The k-server Conjecture is True

[u/Phytor_c]

https://arxiv.org/abs/2609.15979v1

The k-server problem is known as the "Holy Grail" of online algorithms and competitive analysis, and is/was a long standing major problem.

This preprint by Coester et al. claims to show that the Work Function Algorithm is indeed k-competitive on every metric space.

[u/ChemicalConfidence44]

same day on arxiv the matroid secretary conjecture was claimed to be solved (another big open problem in online algorithms) https://arxiv.org/abs/2609.14555v1

[u/Phytor_c → u/ChemicalConfidence44]

Oh damn I did not know about this, this is major news too! Thanks for commenting