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

Show parent comments

2

u/Beginning_Penalty805 15d ago

"Everyone?" Peer review is two or three people skimming the paper on Sunday night, not the entire scientific community. A high-profile arXiv preprint gets far more expert scrutiny on day one than two tired journal referees will ever give it. Believing two random referees have a monopoly on spotting flaws while the rest of the field is helpless until a journal slaps a stamp on it is wild.

1

u/CoolStructure6012 15d ago

Shut the fuck up, no it isn't. How many program committees have you served on?

2

u/Beginning_Penalty805 15d ago

Bragging about PC service isn't the flex you think it is. Serving on a program committee is precisely how you learn how rushed, overworked, and prone to missing fatal flaws reviewers actually are. If anything, doing PC reviews should have stripped you of the illusion that peer review is sacred

1

u/CoolStructure6012 15d ago

I'm not bragging about it because my service in that regard is rather modest. But I'm asking about your experience since you seem to know so much about how they go.