35-year-old k-server conjecture finally proved
Original: The k-server conjecture is true
Why This Matters
Settling a 35-year conjecture reframes the theoretical limits of online resource-allocation algorithms.
Researchers Christian Coester, Elias Koutsoupias, and Marek Zbysiński published a proof on arXiv (September 14, 2026) confirming the k-server conjecture: a deterministic online algorithm can achieve competitive ratio k on any metric space, with the work function algorithm shown to satisfy this bound.
The k-server conjecture, one of the most enduring open problems in theoretical computer science, has been proved. Posed roughly 35 years ago, it claims that a deterministic online algorithm can serve k servers on any metric space with competitive ratio k — meaning its cost is at most k times that of the optimal offline algorithm. Coester, Koutsoupias, and Zbysiński demonstrate that the long-studied work function algorithm meets this bound.
The proof hinges on a novel algebraic representation: work functions are encoded as matrices, where minimum and addition operations in optimal-cost definitions map cleanly to matrix addition and multiplication of formal expressions. Each work function value corresponds to the determinant of k columns of that matrix. A request arrival updates the state via a change of basis and row replacement — a compact, elegant mechanism. The amortized analysis relies on a potential function built from a larger matrix whose coordinates are pairs from the original representation. The paper is 22 KB, suggesting a tight, technically dense argument rather than a sprawling case-by-case proof.