Randomized k-server in polynomial time

Conference item

We study the design of computationally efficient randomized algorithms for the k-server problem. Existing randomized algorithms with the best known competitive ratios are, on the one hand, inherently implicit and, on the other hand, employ a rounding scheme that maintains a distribution over exponentially many configurations. In this work, we introduce a derandomization framework that transforms any randomized k-server algorithm on a hierarchically separated tree into one that uses only O(log k) random bits for request sequences of arbitrary length—hence maintaining a distribution over only polynomially many server configurations. Leveraging this black-box derandomization, we obtain the first polynomial-time randomized k-server algorithm on arbitrary n-point metrics with a polylogarithmic competitive ratio. Our results also have implications for the advice complexity of the k-server problem.

Authors: Coester, C; Cosson, R

• Publication status: Accepted
• Peer review status: Peer reviewed
• Acceptance date: 2026-04-20
• Event title: 53rd European Association for Theoretical Computer Science (EATCS) International Colloquium on Automata, Languages, and Programming (ICALP)
• Event location: Surrey, UK
• Event website: https://icalppodcspaa2026.cs.rhul.ac.uk/icalp/
• Event start date: 2026-07-07
• Event end date: 2026-07-10
• Language: English
• Keywords: k-server; online algorithms; computational complexity; randomized complexity; advice complexity