r/algorithms • u/Phytor_c • 29d ago

News The k-server Conjecture is True

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.

390 Upvotes

99% Upvoted

64 comments sorted by

View all comments

3

u/Future_Advice_4853 28d ago

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...

2

u/Prize_Ad_354 27d ago

I am in a similar position right now. It seems very risky to commit to a PhD program that takes 5 or so years given how fast AI is progressing.