The Randomized Competitive Ratio of Weighted $k$-Server on Uniform Metrics: Closing the Gap between $\Omega(2^k)$ and $\exp(O(k^2))$

The weighted $k$-server problem gives the classical $k$ servers weights $w_1 \le \dots \le w_k$, so that moving server $i$ costs $w_i$ times the distance traveled; on uniform metrics it is a natural weighted paging analogue. Its deterministic competitive ratio on uniform metrics is doubly exponential in $k$, while the best randomized bounds against an oblivious adversary are a lower bound of $\Omega(2^k)$ and, after a 2025 breakthrough that broke the doubly exponential barrier, an upper bound of $\exp(O(k^2))$. This problem asks for the exact asymptotic dependence on $k$ of the randomized competitive ratio of weighted $k$-server on uniform metrics, i.e. for matching upper and lower bounds on that ratio. The source paper (SODA 2026) poses two further companion directions, the trade-off between memory usage and competitive ratio and extensions to metric classes of unbounded aspect ratio such as lines and trees.

Background

In the $k$-server problem, introduced by Manasse, McGeoch, and Sleator (1988), $k$ mobile servers occupy points of a metric space and an adversary reveals a sequence of requests, one point at a time; after each request the algorithm must ensure that some server sits on the requested point, paying the distance that server travels. An online algorithm must act without seeing future requests, so it is compared to the optimal offline solution through the competitive ratio: the worst case, over all finite request sequences, of the ratio of the algorithm's cost to the offline optimum. For randomized algorithms the standard benchmark is the oblivious adversary, who knows the algorithm but cannot observe the outcomes of its random choices; the ratio is then taken on expected cost. On a uniform metric, where all pairwise distances between distinct points are 1, the unweighted problem is exactly the paging (caching) problem, whose deterministic competitive ratio is exactly $k$ and whose randomized competitive ratio is exactly the $k$-th harmonic number.

The weighted $k$-server problem, considered since the early 1990s and first studied systematically by Fiat and Ricklin (1994), gives the servers non-identical weights $w_1 \le \dots \le w_k$: moving server $i$ across distance $d$ costs $w_i \cdot d$. On a uniform metric, moving server $i$ to a requested unoccupied point costs exactly $w_i$, so the problem becomes a paging variant in which the cost of a replacement depends on which server (memory location) performs it. The target is competitive ratios that depend on $k$ alone, not on the weights, the number of points, or the distances; this requirement makes the problem notoriously hard. Whereas the work function algorithm of Koutsoupias and Papadimitriou (1995) is $(2k-1)$-competitive for the unweighted problem on every metric space, no competitive algorithm is known for weighted $k$-server on arbitrary metrics for any $k > 2$ (for $k = 2$ a deterministic 879-competitive algorithm follows from the work of Sitters and Stougie on the generalized two-server problem).

Even on uniform metrics the weighted problem is delicate. Fiat and Ricklin gave a deterministic algorithm whose competitive ratio grows doubly exponentially in $k$, and Bansal, Elias, and Koumoutsos (FOCS 2017) proved a doubly exponential deterministic lower bound that essentially matches it, so randomization is the only route to singly exponential guarantees. Before 2025 the randomized picture was wide open: the only nontrivial randomized algorithms were the memoryless ones of Chiplunkar and Vishwanathan (2020), which are doubly-exponentially competitive and only against the stronger adaptive online adversary (who may observe previous random choices), while the best lower bound was the logarithmic one inherited from unweighted paging. Ayyadevara and Chiplunkar (ESA 2021) improved the lower bound to $\Omega(2^k)$, and Ayyadevara, Chiplunkar, and Sharma (FSTTCS 2024) decomposed the problem into two relaxations whose competitive ratios multiply to bound the original, solving one of them with an $\exp(O(k^2))$-competitive algorithm while leaving the other open. Bijoy, Mondal, and Chiplunkar (SODA 2026) then gave an $\exp(O(k^2))$-competitive randomized algorithm against the oblivious adversary, the first singly exponential upper bound, breaking the doubly exponential barrier for the first time; it works through a recursively defined notion of a phase that simultaneously forces a lower bound on the offline optimum's cost and admits a randomized online strategy of bounded expected cost.

The same paper lifts its algorithm to the generalized $k$-server problem on weighted uniform metrics, in which $k$ servers move in $k$ pairwise-disjoint uniform metric spaces (server $s_\ell$ moves in the $\ell$-th space, where distinct points are at distance $w_\ell$), and each request is a $k$-tuple of points, one per space, served by ensuring that for some $\ell$ the server $s_\ell$ sits on the requested point of its own space. Bansal, Elias, Koumoutsos, and Nederlof (2023) had asked whether an $\exp(k)$-competitive algorithm exists for this generalized problem; the new $\exp(O(k^2))$ result 'almost solves' their question, and weighted $k$-server reduces to the generalized problem, so both carry the same current bounds.

What remains is the precise rate. The randomized competitive ratio of weighted $k$-server on uniform metrics lies between $\Omega(2^k) = \exp(\Omega(k))$ and $\exp(O(k^2))$: it could be $\exp(\Theta(k))$, $\exp(\Theta(k^2))$, or intermediate (for instance $\exp(\Theta(k \log k))$), and no current evidence separates these possibilities. This gap is the last quantitative unknown for the problem on uniform metrics. It contrasts with the unweighted setting on general metrics, where Bubeck, Coester, and Rabani (STOC 2023) disproved the randomized $k$-server conjecture with an $\Omega(\log^2 k)$ lower bound. Beyond uniform metrics almost nothing is known for the weighted problem: Chrobak and Sgall (2004) showed that randomized memoryless algorithms are not competitive on the line metric even for two weighted servers, and Gupta, Kumar, and Panigrahi (2023) showed that the problem becomes tractable only under resource augmentation, where $2\ell$ extra servers ($\ell$ being the number of distinct server weights) bring the competitive ratio down to $O(\ell^2 \log \ell)$.

Problem Statement

Determine the randomized competitive ratio of the weighted $k$-server problem on uniform metrics, against an oblivious adversary, as a function of the number of servers $k$; specifically, close the remaining exponential gap between the best lower bound $\Omega(2^k)$ (Ayyadevara and Chiplunkar, 2021) and the best upper bound $\exp(O(k^2))$ (Bijoy, Mondal, and Chiplunkar, 2025).

The setting: $k$ servers with weights $w_1 \le \dots \le w_k$ occupy points of a uniform metric space (all pairwise distances 1, arbitrarily many points); requests arrive one at a time, each to a point that must be occupied by some server, and moving server $i$ to a new point costs $w_i$; the algorithm must decide its moves without knowledge of future requests, and its competitive ratio is the worst case over request sequences of the ratio of its expected cost to the optimal offline cost. The quantity to determine is the infimum, over randomized online algorithms, of this competitive ratio, as a function of $k$ alone, valid for arbitrary server weights and arbitrarily large metric spaces.

Determining the randomized competitive ratio of weighted $k$-server on uniform metrics means identifying a function $g(k)$ such that the optimal randomized competitive ratio equals $\exp(\Theta(g(k)))$; the ratio is known to lie between $\Omega(2^k)$ and $\exp(O(k^2))$. The same gap, with the same known bounds, also stands for the generalized $k$-server problem on weighted uniform metrics, subsuming the question of Bansal, Elias, Koumoutsos, and Nederlof (2023) on the existence of an $\exp(k)$-competitive algorithm for that problem; an answer for the weighted $k$-server quantity above may resolve both settings simultaneously.

References

1. Adithya Bijoy, Ankit Mondal, Ashish Chiplunkar. Weighted $k$-Server Admits an Exponentially Competitive Algorithm. arXiv:2507.12130 (v1 16 Jul 2025, v2 26 Oct 2025), DOI 10.48550/arxiv.2507.12130, https://arxiv.org/abs/2507.12130. Accepted at SODA 2026.
2. Amos Fiat, Moty Ricklin. Competitive algorithms for the weighted server problem. Theoretical Computer Science 130(1):85-99, 1994. DOI 10.1016/0304-3975(94)90154-6, https://doi.org/10.1016/0304-3975(94)90154-6.
3. Mark Manasse, Lyle McGeoch, Daniel Sleator. Competitive algorithms for on-line problems. STOC 1988, pages 322-333. DOI 10.1145/62212.62243, https://doi.org/10.1145/62212.62243.
4. Elias Koutsoupias, Christos H. Papadimitriou. On the k-server conjecture. Journal of the ACM 42(5):971-983, 1995. DOI 10.1145/210118.210128, https://doi.org/10.1145/210118.210128.
5. Nikhil Bansal, Marek Elias, Grigorios Koumoutsos. Weighted k-Server Bounds via Combinatorial Dichotomies. FOCS 2017, pages 493-504. DOI 10.1109/FOCS.2017.52, https://doi.org/10.1109/FOCS.2017.52; arXiv:1704.03318, https://arxiv.org/abs/1704.03318.
6. Nikhil Ayyadevara, Ashish Chiplunkar. The Randomized Competitive Ratio of Weighted $k$-Server Is at Least Exponential. ESA 2021, LIPIcs vol. 204, 9:1-9:11. DOI 10.4230/LIPIcs.ESA.2021.9, https://doi.org/10.4230/LIPIcs.ESA.2021.9; arXiv:2102.11119, https://arxiv.org/abs/2102.11119.
7. Nikhil Ayyadevara, Ashish Chiplunkar, Amatya Sharma. A Decomposition Approach to the Weighted $k$-server Problem. FSTTCS 2024, LIPIcs vol. 323, 6:1-6:17. DOI 10.4230/LIPIcs.FSTTCS.2024.6, https://doi.org/10.4230/LIPIcs.FSTTCS.2024.6; arXiv:2410.06485, https://arxiv.org/abs/2410.06485.
8. Ashish Chiplunkar, Sundar Vishwanathan. Randomized Memoryless Algorithms for the Weighted and the Generalized k-server Problems. ACM Transactions on Algorithms 16(1), Article 14, 2020. DOI 10.1145/3365002, https://doi.org/10.1145/3365002.
9. Marek Chrobak, Jiri Sgall. The weighted 2-server problem. Theoretical Computer Science 324(2-3):289-312, 2004. DOI 10.1016/j.tcs.2004.05.020, https://doi.org/10.1016/j.tcs.2004.05.020.
10. Nikhil Bansal, Marek Elias, Grigorios Koumoutsos, Jesper Nederlof. Competitive Algorithms for Generalized k-Server in Uniform Metrics. ACM Transactions on Algorithms 19(1), Article 8, pages 8:1-8:15, 2023. DOI 10.1145/3568677, https://doi.org/10.1145/3568677.
11. Anupam Gupta, Amit Kumar, Debmalya Panigrahi. Efficient Algorithms and Hardness Results for the Weighted $k$-Server Problem. APPROX/RANDOM 2023, LIPIcs vol. 275, pages 12:1-12:19. DOI 10.4230/LIPIcs.APPROX/RANDOM.2023.12, https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2023.12; arXiv:2307.11913, https://arxiv.org/abs/2307.11913.
12. Christian Coester, Tze-Yang Poon. Online 3-Taxi on General Metrics. SODA 2026. arXiv:2510.25861, https://arxiv.org/abs/2510.25861, DOI 10.48550/arxiv.2510.25861.
13. Sebastien Bubeck, Christian Coester, Yuval Rabani. The Randomized k-Server Conjecture Is False!. STOC 2023, pages 581-594. DOI 10.1145/3564246.3585132, https://doi.org/10.1145/3564246.3585132.
14. Christian Coester, Romain Cosson. Randomized $k$-server in polynomial time. arXiv:2605.01497 (2026), https://arxiv.org/abs/2605.01497, DOI 10.48550/arxiv.2605.01497.
15. Rene A. Sitters, Leen Stougie. The generalized two-server problem. Journal of the ACM 53(3):437-458, 2006. DOI 10.1145/1147954.1147960, https://doi.org/10.1145/1147954.1147960.