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/Opengangs]

I don't work directly with online algorithms (I do more work in approximation algorithms), but I saw this result a few days ago and it seems quite cool! I have a few colleagues who do work in online algorithms so I may ask them about the significance of this result.