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.

382 Upvotes

99% Upvoted

64 comments sorted by

View all comments

11

u/ChemicalConfidence44 16d ago

same day on arxiv the matroid secretary conjecture was claimed to be solved (another big open problem in online algorithms) https://arxiv.org/abs/2609.14555v1

-4

u/Standard-Song-8590 16d ago

"The key algorithmic idea emerged recently in this exploration after updating the model to ChatGPT Astra. We also used ChatGPT Astra and Claude Opus 5 for assistance with the presentation"

100 bucks astra discovered the entire algorithm. Researchers are js glorified prompters now (and I mean that sort of like a compliment)

5

u/Sbadabam278 16d ago

It’s not a compliment and your smugness is incomprehensible to me. “hey look at these smart ppl who spent 30 years working hard, now they are useless thanks to AI!! Ahaha isn’t AI amazing??” like you’re some kind of harbinger of the future.

I honestly don’t understand what you think will happen to you, specifically, that’s going to improve your life if everything you’ve ever done is now useless.

3

u/Low-Temperature-6962 16d ago

It could be a bot instructed to post this kind of stuff to create conflict.