Tight Bounds for Randomized Generalized k-Server on Uniform Metrics
cs.DS
Submitted: 2026-10-27
Updated: 2026-10-27
Comments: 24 pages, 3 figures
License: http://creativecommons.org/licenses/by/4.0/
The gist: In the generalized k-server problem, each of k servers moves in its own metric space, and a request (r 1,,r k) is served once some server i stands at the point r i of its space.
Abstract
In the generalized k-server problem, each of k servers moves in its own metric space, and a request (r 1,,r k) is served once some server i stands at the point r i of its space. We determine the randomized competitive ratio against an oblivious adversary when every space is a uniform metric. With unit distances the ratio is Θ(k k): we give a (k+1) (2k) -competitive algorithm and show that for large k every algorithm has ratio at least 1 over 20k k, improving the bounds O(k squared k) and Ω(k) of Bienkowski, Jeż, and Schmidt. When server i pays w i per move, the ratio is (Θ(k)): we give a 20 k-competitive algorithm, which also applies to weighted k-server on uniform metrics. This improves the (O(k 2)) bound of Bijoy, Mondal, and Chiplunkar and matches the Ω(2 k) lower bound of Ayyadevara and Chiplunkar up to the base of the exponent. Both algorithms follow normalized weights exactly, through couplings whose expected movement is controlled by the decrease of the logarithm of the total weight. The lower bound hides a random permutation among the solutions of random permutation constraints, which split into small, well-separated components, and then forbids one position to one server at a time.
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles