# The k-server conjecture just fell

> One of the oldest open problems in online algorithms now has a proof, and the winning algorithm was sitting there all along.
- Title: The k-server conjecture just fell · arXiv | Shortify
- Summary: One of the oldest open problems in online algorithms now has a proof, and the winning algorithm was sitting there all along. The work function algorithm is…
- Keywords: algorithms, k-server problem, online algorithms, theory, competitive analysis, technology, startups, k-server, conjecture, just, fell, arXiv
- Source: arXiv — https://arxiv.org/abs/2609.15979
- Read time: 1 min
- Topics: algorithms, k-server problem, online algorithms, theory, competitive analysis, technology, startups
## What the conjecture claims
With k servers moving around a metric space to answer requests, a deterministic algorithm with no view of the future should still cost at most k times the best offline plan. On every metric space, no exceptions.

> a deterministic online algorithm can achieve competitive ratio $k$ on every metric space
## Now it is proven
Christian Coester, Elias Koutsoupias and Marek Zbysiński posted the proof to arXiv on 14 September 2026. Three sentences of abstract close a question the field has chased for decades.

> We prove the conjecture.
## The old algorithm wins
No new method was needed. The work function algorithm, long suspected to be the answer, is the one shown to hit ratio k everywhere.

> we show that the work function algorithm satisfies it
## Write it as a matrix
The proof reframes the work function algebraically. A matrix holds every feasible path to reach a given server configuration, so the combinatorics turn into linear algebra.

> a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration
## Costs become determinants
The minimum and addition that define optimal cost map onto addition and multiplication of formal expressions. Each work function value then reads off as the determinant of k columns.
## Each request shifts the basis
A new request updates the matrix by a change of basis plus a row replacement. The amortized analysis rides on a potential function built from a larger matrix whose coordinates are pairs of the original ones.
## Key takeaway

The work function algorithm is k-competitive on every metric space, proved by rewriting work functions as matrices and cost values as determinants.