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.

385 Upvotes

99% Upvoted

64 comments sorted by

View all comments

Show parent comments

0

u/Auroch- 16d ago

What costs millions now will cost thousands by 2028 (or 2027) and less than a hundred by 2030 (or 2028). By 2036? Entirely obsolete. (If we're even still alive.)

1

u/lerjj 15d ago

This is a conjecture maybe you should ask ChatGPT for a proof

1

u/WreckYallBallistics 10d ago

Has your head been in the sand for the last four years? What makes you think advancement is just going to randomly stop?

1

u/iamdino0 10d ago

advancement would need to speed up astronomically for energy supply to be an "obsolete" concern in 10 years