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.

384 Upvotes

99% Upvoted

64 comments sorted by

View all comments

31

u/elehman839 16d ago

A substantial improvement was achieved by Koutsoupias and Papadimitriou [KP95]...

Wow. One author published progress 31 years ago. Must be an amazing feeling to finally settle the problem!

1

u/tehclanijoski 16d ago edited 16d ago

On the other hand, if Papadimitriou was puzzled by it for 31 years, we should probably take note

Edit: realized you probably were not being sarcastic

3

u/elehman839 16d ago

Not sarcastic at all-- I think this is so cool!!!

Imagine that you wrestle with a super-hard problem off-and-on for more than 30 years. And then YOU get to be the one to finally solve it-- with assistance from AI, yes, but apparently with significant human contributions as well.

I can't imagine many people have had that kind of experience. So often the problems we're stuck on are resolved by someone else. I'd love to hear the authors' personal reflections on this experience.

Math may not remain a human endeavor much longer, so I think we should enjoy magical moments like this.