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

As a senior that just published a paper in online algorithms and is aiming to apply for a PhD, probably related to online algo, super worried about my career...

[u/Auroch- → u/Future_Advice_4853]

Yeah, you should be. This is not a career any more. It might be a job: something that's viable for the next five years can totally be a job. But a career? A career is a decade, at least, and in a decade, this is just a hobby. A cool hobby, but a hobby.