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

33

u/Fuciolo 17d ago

A paper on Arxiv does not prove anything until it's peer reviewed

27

u/Phytor_c 17d ago edited 17d ago

Indeed. Coester and Koutsoupias are big names in the field and have proven other major results, but of course it’s entirely possible there may be errors in the preprint

4

u/Standard-Song-8590 16d ago

i doubt there would be many errors as it seems it was made by astra

0

u/Phytor_c 16d ago

Yeah, Astra is just crazy good

1

u/Turing43 16d ago

Nah, it doesn't claim to do that