Optimal-order randomized k-server on arbitrary metrics
OpenAI research collection · 2 manuscripts · Source checked 2026-10-19
OpenAI's result summary
Establishes a randomized competitive ratio O(log^2(k+1)) for k-server on every metric space, matching the worst-case lower-bound order. One policy serves every finite oblivious request sequence, including on infinite unbounded metrics. On finite rational metrics, a uniform implementation has polynomial preprocessing and per-request bit cost in the input length and log(t+1) at request t, with a finite instance-dependent additive movement constant.
Read the manuscripts
Short excerpts below come from OpenAI's abstracts. The full abstract and original PDF preserve the paper's precise scope.
MANUSCRIPT 01
Squared-logarithmic randomized k-server on arbitrary metrics
We prove that randomized k-server has competitive ratio O((log(k+1))^2) on every metric space against oblivious request sequences, matching the known worst-case lower bound. For each metric and initial configuration, one policy works for all finite request sequences, including on infinite and unbounded spaces. When the initial…
Full source abstract
We prove that randomized k-server has competitive ratio O((log(k+1))^2) on every metric space against oblivious request sequences, matching the known worst-case lower bound. For each metric and initial configuration, one policy works for all finite request sequences, including on infinite and unbounded spaces. When the initial server positions are distinct, no additive term is needed.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
Uniform computation of the squared-logarithmic k-server bound
We construct a uniform randomized k-server algorithm on finite rational metrics with competitive ratio O(log^2(k+1)) against oblivious request sequences. Preprocessing is polynomial in the input length, and per-request bit complexity is polynomial in that length and the binary request-counter length. The additive movement…
Full source abstract
We construct a uniform randomized k-server algorithm on finite rational metrics with competitive ratio O(log^2(k+1)) against oblivious request sequences. Preprocessing is polynomial in the input length, and per-request bit complexity is polynomial in that length and the binary request-counter length. The additive movement constant is finite and instance-dependent, but may be enormous. The construction uses the companion squared-logarithmic existence theorem.
This exact PDF is not listed in the imported formalization catalogue. Family scope notes may contain further information.
New mathematical reasoning could help AI tackle harder scientific and computational problems. How reliably these skills transfer beyond mathematics will determine how much they contribute to general intelligence.