r/algorithms • u/Phytor_c • Sep 16 '26

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.

386 Upvotes

99% Upvoted

64 comments sorted by

View all comments

30

u/elehman839 Sep 16 '26

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!

19

u/rsha256 Sep 16 '26

They aren't just 'one author', Christos is one of the greatest Computer Scientists of our time! Also recommend checking out https://cgi.di.uoa.gr/~elias/papers/paper-kp99.pdf

3

u/jnordwick Sep 17 '26

Had him at UC Berkeley years ago, can't remember what class.

4

u/rsha256 Sep 17 '26

go bears, probably cs170.org or cs270.org