A preprint claims a proof of the k-server conjecture, arguing the work function algorithm is k-competitive on every metric space

Sources: primary, discussion
Summary: Christian Coester, Elias Koutsoupias and Marek Zbysinski submitted the preprint to arXiv cs.DS on 2026-09-14, stating a proof of the k-server conjecture, which holds that a deterministic online algorithm can reach competitive ratio k on every metric space, by showing the work function algorithm satisfies that bound. The proof represents the work function as a matrix encoding all feasible paths to a configuration, so each work function value is the determinant of k columns and a request arrival updates the representation by a change of basis and a row replacement, with the amortized analysis resting on a potential function over a larger matrix. The preprint is not peer reviewed and no third party has verified it.
Why it matters: The k-server problem generalizes paging and cache eviction, so the ratio it settles is the worst-case bound on the online decision an eviction policy makes.
Follow-up: Track a referee report or an independent verification of the proof.