The k-server conjecture is true
After decades of partial results, Christian Coester, Elias Koutsoupias, and Marek Zbysiński prove the k-server conjecture: the deterministic work-function algorithm is k-competitive on every metric space. Their proof represents the work function as a matrix, turns request updates into basis changes and row replacements, and derives the amortized bound from a larger matrix-valued potential.
HN readers called it a long-sought “holy grail” of competitive analysis and translated the online/offline guarantee into dispatching examples; discussion also noted that the abstract is unusually opaque to non-specialists.