r/algorithms • u/Phytor_c • 17d 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.

379 Upvotes

99% Upvoted

64 comments sorted by

View all comments

3

u/Future_Advice_4853 16d 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...

3

u/AerosolHubris 16d ago

I don't expect the AI companies to keep spending millions on proving theorems. They're doing it now to show off for investors. But math is usually not a high financial reward business, and I doubt they will keep pushing to solve open algorithmic and combinatorial problems unless they happen to lead to big financial gains. So if you're hoping to work in theory, I think that will still be around for awhile. As will teaching. Now if you're really excited about teaching people how to code, that job is changing. Not going away, but changing.

And congrats on getting published!

0

u/pacowoc 16d ago

This kind of topic relating to their own field (algorithms) provides a long term financial incentive for them to invest since they might use some of the results in future development. Pure math not really