k-server conjecture proven true: work function algorithm achieves competitive ratio k
ctjlewis · x · 2026-09-16
A new arXiv paper by Christian Coester, Elias Koutsoupias, and Marek Zbysiński proves the long-standing k-server conjecture: a deterministic online algorithm can achieve competitive ratio k on every metric space. The proof uses the work function algorithm, representing the work function as a matrix where feasible paths map to formal expressions and each value corresponds to a determinant of k columns; requests update the representation via change of basis and row replacement, with amortized analysis via a potential function on a larger matrix.
Related event: Decades-Old k-Server Conjecture Proven on arXiv(3 posts)→
More from Research
- A Millennium Prize Problem, two AI labs, and a credit fight over Navier-Stokes — thursdai_pod · 2026-09-16
- MICAFlow: fast and robust MRI preprocessing pipeline bridges neuroimaging research and clinical practice — bttyeo · 2026-09-16
- Self-evolving agent framework Épi hits 120 research records, tightens Klarner's constant — my_cat_can_code · 2026-09-16
- Foundation funds OpenADMET: open datasets and blind competitions to crack drug ADMET prediction — iskander · 2026-09-16
- Judea Pearl challenges Solomonoff induction fans: solve the firing squad problem first — yudapearl · 2026-09-16
- Geodes paper: selective generalization of misalignment via token-marked midtraining — sebkrier · 2026-09-16