{"id":"openai-math/Uniform-computation-of-the-squared-logarithmic-k-server-bound","pdf":"https://github.com/openai/math/blob/main/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026","tags":["online-algorithms","k-server","competitive-analysis","randomized-algorithms"],"score":0,"title":"Uniform computation of the squared-logarithmic k-server bound","domain":"Theoretical computer science","family":"110","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{},"formalized":false,"family_title":"Optimal-order randomized k -server on arbitrary metrics"}