The $k$-server conjecture is true
Christian Coester, Elias Koutsoupias, Marek Zbysiński
cs.DS
2026-09-15
Oxford researchers prove the work function algorithm is k-competitive on every metric, with an additive clique-weight constant, settling the 1988 k-server conjecture.
The k-server problem is easy to state. k servers sit in a metric space. Requests arrive one point at a time. Each request must be served immediately by moving some server there. The objective is total distance traveled. An online algorithm cannot see the future, so it is judged by its competitive ratio against an offline optimum that knows the whole sequence.
Manasse, McGeoch, and Sleator proved in 1988 that every deterministic online algorithm has competitive ratio at least k on any metric with more than k points. They showed the bound is tight for k=2 and for (k+1)-point spaces, and conjectured tightness in general. That claim became the k-server conjecture, often called the holy grail of competitive analysis.
The first finite ratio on general metrics was exponential in k. In 1995 Koutsoupias and Papadimitriou proved that the work function algorithm (WFA) is (2k−1)-competitive. That remained the best deterministic bound on general metrics for 31 years. The ratio k itself was known only on special spaces: the line and trees via Double Coverage, weighted stars (weighted paging), n=k+2, and k=3 on the Manhattan plane, trees, and circles.
WFA is one rule. For each configuration X of k server locations, the work function wt(X) is the cheapest offline cost to serve the first t requests and finish at X. These values can be maintained online by dynamic programming. On each request, WFA moves to a configuration that minimizes work-function value plus the move cost from the current position.
The actual movement cost is awkward to bound directly. Chrobak and Larmore's extended-cost accounting replaces it with the largest one-step increase of the work function over all configurations. A potential Ψ then has to satisfy three inequalities: its start value equals minus the initial clique weight, each request increases Ψ by at least the extended cost, and Ψ never exceeds (k+1) times the work function minus the clique weight of the current configuration. Subtracting the terminal work function drops the ratio from k+1 to k.
The potential in this paper lives in an algebraic encoding, not in ordinary reals. Each point x gets a column vector qx in k dimensions, with entries that are formal expressions whose exponents record cost. The work function of a k-set is the valuation of the determinant of those k columns: the lowest exponent that appears. Min and addition in the original recurrence become ordinary addition and multiplication. Independent coefficient variables stop equal-cost matchings from cancelling inside the determinant.
A request is processed in two linear-algebra steps. First a change of basis sends the requested column to the first unit vector while leaving every k-column determinant unchanged. Then the first row of every column is replaced by a quantity whose valuation equals distance to the request. Expanding the new determinant along that row reproduces the work-function recurrence exactly.
The potential is built from pairwise products of these columns, sitting in a space of dimension k(k+1)/2, each pair weighted by a negative power of the formal cost variable. Ψ is the minimum valuation among maximal minors of that larger matrix. A classical identity says the determinant of the symmetric square is the original determinant to the power k+1. That is where the (k+1) in the potential bound comes from. After a request, the rise in Ψ covers the extended cost.
The authors are explicit about how the argument was found. They first designed a potential that works for k=3 on arbitrary metrics and verified it by showing a large family of linear programs infeasible, with no AI involved. Discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro led to a more symmetric potential and a second proof for k=3. ChatGPT 6 Astra then produced an algebraic proof for general k. The authors supplied an explicit column representation of work functions; the model adapted the earlier argument and drafted some sections, which the authors revised.
For every metric space and every finite request sequence,
cost of WFA ≤ k · OPT + cl(C0),
where cl(C0) is the sum of pairwise distances among the k initial server locations. The competitive ratio is therefore k. The additive term depends only on the opening configuration.
| Result | Ratio | Scope |
| Deterministic lower bound (1988) | ≥ k | any metric with n > k |
| Fiat–Rabani–Ravid (1990) | exponential in k | general metrics |
| WFA, Koutsoupias–Papadimitriou (1995) | 2k−1 | general metrics |
| WFA, this paper | k | general metrics |
Randomization is a separate story. O(log k) randomized algorithms exist on uniform metrics and weighted stars, matching an Ω(log k) lower bound. The conjecture that O(log k) holds on every metric is already false: Bubeck, Coester, and Rabani proved an Ω(log² k) lower bound on some spaces. When the number of points or the aspect ratio can be infinite, it is still open whether randomness helps at all. Even with randomization allowed, the best published ratio on general metrics remains the k from WFA.
k-server is the flagship model of competitive analysis. Paging is the uniform-metric special case. WFA itself shows up in metrical task systems, layered graph traversal, list update, and convex body chasing. Closing the gap from 2k−1 down to the 1988 lower bound ends a 38-year question.
Nobody should read this as a new cache policy. WFA enumerates k-subsets of the points seen so far; maintaining the work function is expensive. The contribution is a proof. A generic algorithm that applies far beyond k-server is already deterministically optimal on the cleanest instance of the family.
The encoding also identifies k-server work functions with valuated matroids, tropical Plücker relations, and the gross-substitutes condition in economics. Anyone who wants to move the same potential onto weighted k-server or k-taxi will start from this representation.
The argument is valuation, determinants, and the symmetric square, not a short combinatorial potential one could check on a blackboard in an afternoon. Independent verification is needed, and the acknowledgments already say so: the algebraic proof for general k was derived by ChatGPT 6 Astra, and some sections were machine-drafted. The k=3 potential and the LP infeasibility check are the authors' own work. The jump from 3 to arbitrary k, as a public object, is this 18-page paper.
Computational cost of WFA is untouched. Ratio k is optimal in the information-theoretic sense. It does not give a polynomial-time deterministic online algorithm with that guarantee.
Weighted k-server, generalized k-server, and k-taxi remain open. Whether randomization helps on infinite metrics is also open. The additive clique weight can be large if the initial servers sit far apart, even though it does not change the competitive ratio.