Family 110Theoretical computer scienceNo LeanNot yet digested
Optimal-order randomized k-server on arbitrary metrics
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.
Manuscripts in this family · 2
Squared-logarithmic randomized k-server on arbitrary metrics
Sep 24, 2026·Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf
We 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
Sep 24, 2026·Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdf
We 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.