1 · The essentials
Imagine managing movable servers, each of which can travel to places where service is requested. The goal is to keep their total travel small even though future requests are unknown. The main manuscript gives a randomized rule whose expected travel is within a factor of order of the best plan that knows all the requests in advance. This guarantee applies to every space with distances, even one with infinitely many locations or no bound on how far apart they can be. The requests must be fixed independently of the rule’s random choices, and one rule handles every finite list of requests from a given starting arrangement. The factor matches the known worst-case lower bound in its order of growth, and no extra travel allowance is needed when the starting server positions are distinct. A companion manuscript gives a computationally efficient version for finite spaces with rational distances, although its extra travel allowance can be enormous.
A picture to help (an imperfect image, not to be taken literally)
As an imperfect image, think of dispatching a fleet of repair vans without knowing tomorrow’s calls, then comparing their total driving with a planner who knew the entire call list. The result limits how much worse a randomized dispatch rule can be, provided the call list is not tailored to its random decisions; the image does not capture the full range of distance spaces covered.
Why it matters
The result reaches the known worst-case order of performance while applying to arbitrary metric spaces, rather than only finite or bounded ones. The companion manuscript also addresses the gap between the existence of a good policy and a uniform way to compute its decisions. Its potentially enormous additive movement constant is an important qualification to that computational guarantee.
2 · Going further
In the -server problem, requests specify locations in a metric space, and servers must move to serve them while minimizing total movement. Competitive analysis compares a policy’s expected movement with the minimum movement achievable with advance knowledge of the sequence, allowing an additive term where specified. The main manuscript gives a randomized competitive ratio against oblivious request sequences—sequences fixed independently of the policy’s random choices. The source identifies this as matching the known worst-case lower-bound order, not as an exact constant-factor equality.
The existence statement has an important uniformity requirement: for each metric space and initial configuration, a single policy must work for all finite request sequences. It includes infinite and unbounded metric spaces. When the initial positions of the servers are distinct, the main manuscript states that no additive term is needed. The supplied abstract does not describe the argument establishing this existence theorem, so no particular proof mechanism can be extracted from it.
The companion manuscript uses that existence theorem to construct a uniform randomized algorithm on finite rational metrics. Preprocessing has polynomial bit complexity in the input length, and processing request has polynomial bit complexity in the input length and , the order of the binary request-counter length. It retains the squared-logarithmic competitive ratio but allows a finite, instance-dependent additive movement constant that may be enormous. The main result has a Lean formalization; the supplied source does not specify its detailed coverage, so that verification should not be extended automatically to every companion claim.
Useful notions
- Distances and metric spaces
- Online decisions without future knowledge
- Expected cost of a randomized rule
- Comparison with an advance-informed optimum
- Polynomial bit complexity
What was known before / what is new
Before
The source states that a worst-case lower bound of squared-logarithmic order was already known. It supplies no further historical account or description of earlier algorithms.
New
The main manuscript establishes a matching-order randomized guarantee on every metric space, with one policy serving all finite oblivious request sequences from a given initial configuration. It also states that distinct initial server positions eliminate the need for an additive term. The companion manuscript turns the existence result into a uniform algorithm for finite rational metrics with polynomial preprocessing and per-request bit complexity.
Limits and assumptions
The guarantees concern finite oblivious request sequences, not requests chosen in response to the policy’s random choices. Matching the worst-case lower-bound order does not assert an exact optimal constant or a matching lower bound on every individual metric. The no-additive-term statement requires distinct initial server positions. The computational result is restricted to finite rational metrics and permits a finite but potentially enormous instance-dependent additive movement constant. The main result has a Lean formalization, but the supplied source does not identify its exact scope or establish that it covers all computational claims. No remaining open problem is specified in the supplied abstracts.
Mini glossary
- Metric space —
- A collection of locations equipped with distances satisfying the usual distance rules, including the triangle inequality.
- Competitive ratio —
- A factor bounding a policy’s cost relative to the best cost with advance knowledge of the requests, with an additive allowance when specified.
- Oblivious request sequence —
- A request sequence fixed independently of the randomized policy’s choices.
- Additive movement constant —
- An extra movement allowance in the comparison with the advance-informed optimum, independent of the request sequence.
- Finite rational metric —
- A metric space with finitely many locations and rational-valued distances.
- Bit complexity —
- Computational cost measured in operations on the binary representation of the data.
Keywords : k-server · Randomized competitive analysis · Metric spaces
AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.
3 · Technical details and sources
Claim made in the manuscript (source text)
Establishes a randomized competitive ratio for k-server on every metric space, matching the worst-case lower-bound order. One policy serves every finite oblivious request sequence, including on infinite unbounded metrics. On finite rational metrics, a uniform implementation has polynomial preprocessing and per-request bit cost in the input length and at request t, with a finite instance-dependent additive movement constant.
Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.
Manuscripts in this family
Squared-logarithmic randomized k-server on arbitrary metrics
24/09/2026We prove that randomized k-server has competitive ratio on every metric space against oblivious request sequences, matching the known worst-case lower bound. For each metric and initial configuration, one policy works for all finite request sequences, including on infinite and unbounded spaces. When the initial server positions are distinct, no additive term is needed.
Uniform computation of the squared-logarithmic k-server bound
24/09/2026We construct a uniform randomized k-server algorithm on finite rational metrics with competitive ratio against oblivious request sequences. Preprocessing is polynomial in the input length, and per-request bit complexity is polynomial in that length and the binary request-counter length. The additive movement constant is finite and instance-dependent, but may be enormous. The construction uses the companion squared-logarithmic existence theorem.