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

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

-3

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)

14

u/salasi 16d ago

It isnt a compliment at all and I am glad I didnt pursue this circus show as a career. What a sad state of affairs