I feel like the paper itself does a fairly good job:
> The [k-server] problem’s definition is simple: There are k servers located at points of
a metric space. At each time step, a request arrives at a point of the metric space. An online
algorithm must serve the request immediately by moving a server to the requested location, without
knowledge of future requests. The goal is to minimize the total distance traveled by servers.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive
ratio k on every metric space.
I only had to look up what "competitive" means in this context, and wikipedia [0] had this to say about it:
> An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
The ratio by which this performance is bounded for a k-competitive algorithm is k (plus some constant) [1]. We can consider the analogy of k support technicians ("servers) located in different (physical) locations ("in metric space"): The conjecture/theorem states that in any metric space (Not necessarily two- or three-dimensional), there exists an online algorithm that results in travelled distances of no more than roughly k times that of the optimal distance if all requests were known in advance.
[0] https://en.wikipedia.org/wiki/Competitive_analysis_(online_a...
[1] https://www14.in.tum.de/personen/albers/papers/brics.pdf Section 1.1
> The [k-server] problem’s definition is simple: There are k servers located at points of a metric space. At each time step, a request arrives at a point of the metric space. An online algorithm must serve the request immediately by moving a server to the requested location, without knowledge of future requests. The goal is to minimize the total distance traveled by servers.
> The k-server conjecture states that a deterministic online algorithm can achieve competitive ratio k on every metric space.
I only had to look up what "competitive" means in this context, and wikipedia [0] had this to say about it:
> An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded.
The ratio by which this performance is bounded for a k-competitive algorithm is k (plus some constant) [1]. We can consider the analogy of k support technicians ("servers) located in different (physical) locations ("in metric space"): The conjecture/theorem states that in any metric space (Not necessarily two- or three-dimensional), there exists an online algorithm that results in travelled distances of no more than roughly k times that of the optimal distance if all requests were known in advance.
[0] https://en.wikipedia.org/wiki/Competitive_analysis_(online_a...
[1] https://www14.in.tum.de/personen/albers/papers/brics.pdf Section 1.1