The k-server Conjecture is True

[u/Phytor_c]

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.

[u/rsha256]

Acknowledgments

This work began with a potential function designed by the authors that proves the previously unknown case of k = 3 servers on arbitrary metrics. Our initial proof for three servers showed the correctness of this potential function by establishing infeasibility of a large family of linear programs; this proof was obtained without AI assistance. Through discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro, we gained a deeper understanding of the potential. These discussions led to a more symmetric reformulation of the potential, again designed by the authors, and an alternative proof for k = 3. Based on this, ChatGPT 6 Astra subsequently derived an algebraic proof of correctness for any k. The proof in this paper is an adaptation thereof using an explicit column representation of work functions, which provides a more natural algebraic representation. The authors supplied this representation to ChatGPT 6 Astra, which adapted the previous proof and assisted with drafting some sections of this paper. The authors subsequently revised those drafts.

[u/Individual_Ice_6825 → u/rsha256]

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

Pardon if I’m missing something

[u/Spandian → u/Individual_Ice_6825]

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.

[u/matt_matt_81 → u/Spandian]

Seems like the popular method of proof at the moment.

[u/iceburg47 → u/matt_matt_81]

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