VibeMathedMath problems solved with AI
Sign in

Deterministic kk-server conjecture

The kk-server conjecture states that a deterministic online algorithm can achieve competitive ratio kk on every metric space. We prove the conjecture. Specifically, we show that the work function algorithm satisfies it.
Our proof uses a natural algebraic representation of the work function as a matrix, which encodes all feasible paths to reach a configuration. In this representation, the minimum and addition operations arising in the definition of optimal costs correspond to addition and multiplication of formal expressions, and each work function value corresponds to the determinant of kk columns of the matrix. A request arrival updates the representation via a change of basis and row replacement. The amortized analysis is based on a potential function defined in terms of a larger matrix whose coordinates are pairs of coordinates of the original matrix representation.

Result
Proved(see note)
Status
Resolved
AI contribution
—
Method
Argument
Field
Online algorithms
Posed by
Manasse, McGeoch, and Sleator
Year posed
1988
Years open
38y
Solved
2026-09-14
Model
GPT 6 Astra
Vendor
OpenAI
Collaborators
Christian Coester, Elias Koutsoupias, Marek Zbysiński
Verification
Unreviewed
Publication
Preprint
Significance
—
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

The paper proves that the work function algorithm (WFA) is kk-competitive for the kk-server problem on every metric space. Specifically, for initial configuration C0C_0 and every finite request sequence σ\sigma,WFAC0(σ)≤k OPTC0(σ)+cl(C0). \mathrm{WFA}_{C_0}(\sigma)\leq k\,\mathrm{OPT}_{C_0}(\sigma)+\mathrm{cl}(C_0). Since a competitive ratio below kk is impossible in general, this settles the deterministic kk-server conjecture with the optimal ratio.

The proof represents work-function values as valuations of determinants over a formal field and constructs a potential from quadratic products of the determinant columns. Its increase at each request pays the extended cost of WFA, yielding the global bound.

This does not concern the separate randomized kk-server conjecture, which was previously refuted.

What the AI did

The authors first developed, without AI assistance, a potential function proving the previously unknown k=3k=3 case on arbitrary metrics. Discussions with ChatGPT 5.5 Pro and Gemini 3.1 Pro helped them understand and symmetrize that potential. Based on this reformulation, ChatGPT 6 Astra derived an algebraic proof valid for arbitrary kk, thereby supplying the central generalization that proves the conjecture. The paper adapts this proof using an explicit column representation of work functions. After the authors supplied that representation, Astra further adapted the proof and assisted with drafting portions of the paper.

Verification

This is an arXiv v1 preprint claiming a proof of a longstanding major conjecture. The paper contains a complete mathematical argument, but no independent expert verification, peer review, or formal machine-checked proof is identified in the source. The claim should therefore remain classified as unreviewed pending independent scrutiny.

Source

Submitted by VibeGene on

Changelog2 changes

Discussion