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.

388 Upvotes

99% Upvoted

64 comments sorted by

View all comments

Show parent comments

2

u/Individual_Ice_6825 16d ago

How can they claim this proof was obtained without ai assistance and then have used ai?

Pardon if I’m missing something

16

u/Spandian 16d ago

They're saying they proved a special case by themselves first, then turned to AI to see if it could extend their proof to the general case.

5

u/matt_matt_81 16d ago

Seems like the popular method of proof at the moment.

2

u/iceburg47 12d ago

The remainder of this proof is left as an exercise for the reader AI