VibeMathedMath problems solved with AI
Sign in

Randomized k-server on arbitrary metrics: a competitive ratio polylogarithmic in k, of optimal order log^2 k

In the kk-server problem (Manasse, McGeoch and Sleator, 1988), kk servers in a metric space serve online requests, paying the distance moved, against the offline optimum. Against oblivious adversaries the folklore randomized kk-server conjecture predicted ratio O(log⁡k)O(\log k) on every metric; Bubeck, Coester and Rabani (2023) refuted it, exhibiting (k+1)(k+1)-point metrics that need Ω(log⁡2k)\Omega(\log^2k). The best upper bounds depended on the metric: O(log⁡2klog⁡3nlog⁡log⁡n)O(\log^2k\log^3n\log\log n) (Bansal-Buchbinder-Madry-Naor), O(log⁡2k)O(\log^2k) on HSTs and hence O(log⁡2klog⁡n)O(\log^2k\log n) on nn-point metrics (Bubeck-Cohen-Lee-Lee-Madry); Lee's claimed polylog(k)(k) bound was withdrawn. Is there a randomized algorithm with competitive ratio polylogarithmic in kk alone on every metric space, and in particular O(log⁡2k)O(\log^2k)?

Result
Proved(see note)
Status
Candidate (review pending)
AI contribution
AI-discovered
Method
Argument
Field
Online algorithms; competitive analysis
Posed by
Folklore randomized k-server conjecture (O(log k)), refuted by Bubeck, Coester and Rabani; the polylog(k) form pursued by Bansal-Buchbinder-Madry-Naor and Lee
Year posed
—
Years open
—
Solved
2026-09-24
Model
Unreleased internal OpenAI model
Vendor
OpenAI
Collaborators
—
Verification
Lean-checked, statement unaudited
Publication
Announced
Collection
OpenAI math release (October 2026), version adc7f12
Significance
45 / 100
Disclosed cost
—
Wikipedia
No dedicated article

What was actually shown

Theorem 1.1: an absolute CC such that for every k≥2k\ge2, every metric space with at least k+1k+1 points and every start, one randomized online policy has E cost≤C(log⁡(k+1))2OPT+B\mathbb E\,\mathrm{cost}\le C(\log(k+1))^2\mathrm{OPT}+B on every finite oblivious request sequence; BB depends on the instance and is 0 for distinct starting positions. With Bubeck-Coester-Rabani this is the sharp worst-case order. The policy is not claimed efficient; the companion gives polynomial-time preprocessing and per-request cost on finite rational metrics, with a possibly enormous additive constant. It does not determine the optimal ratio on each individual metric, nor the deterministic ratio.

What the AI did

The release README says the results were produced by an unreleased internal OpenAI model with a fixed procedure, on average about three hours of ChatGPT Pro thinking compute per result, and that some outputs build on earlier model results. This result is not among the README's exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored 'OpenAI' and names no human author. The family has two manuscripts dated September 24, 2026: the principal existence theorem and a companion giving a uniform polynomial-time implementation on finite rational metrics, which uses the principal theorem.

Verification

No independent mathematician has checked this yet. Checked here: Theorem 1.1 was read against the question as the manuscript frames it after Bubeck-Coester-Rabani; it gives O(log⁡2(k+1))O(\log^2(k+1)) with an absolute constant on every metric space with at least k+1k+1 points. The proof was not refereed. The challenge lean/ComparatorChallenges/KServer.json (solution module OAI.Combinatorics.KServer.Main, present at the pinned commit) is not in the formalization catalogue; its statement KServer.lean was read here: there is C>0C>0 such that for all k≥2k\ge2, every metric space with an injection of k+1k+1 points and every initial configuration, some history-dependent randomized policy satisfies expected cost ≤C(log⁡(k+1))2⋅OPT+B\le C(\log(k+1))^2\cdot\mathrm{OPT}+B for every finite request list, with B=0B=0 when initial positions are distinct. This states the headline claim. UniformKServer.json covers the companion. Not rebuilt here.

Sources

Changelog1 change

Discussion