{"id":"openai-math/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics","pdf":"https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf","url":"https://github.com/openai/math/tree/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026","tags":["online-algorithms","competitive-analysis","k-server","metric-spaces"],"score":0,"title":"Squared-logarithmic randomized k-server on arbitrary metrics","domain":"Theoretical computer science","family":"110","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"cs.CC","summary":"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.","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"}