Documentary state: DRAFT_UNACCEPTED. This draft has NOT been editorially admitted. Mathematical claims require independent checking.
OAI-26 family 110: randomized k-server on arbitrary metric spaces
Editorial status: DRAFT_UNACCEPTED. NO_CERTIFICATION. This account reports source-pinned publisher claims, not an independently checked competitive-analysis proof.
The question in plain language
Imagine maintaining \(k\) movable servers that must respond to a stream of requests at points of a metric space. Whenever a request arrives, a server must be placed at its location, and moving a server costs the distance traveled. An online algorithm must decide without knowing future requests, while an offline benchmark knows the entire sequence.
The competitive ratio measures how much more movement the online policy may incur than the optimum offline solution. Family 110 claims a randomized policy with squared-logarithmic dependence on \(k\) for arbitrary metric spaces, including infinite and unbounded ones.
A small example
With two servers on a line, a request arriving far from both servers forces a choice about which server to move. Moving the nearest server is locally appealing but can be costly if later requests concentrate near the server's former location.
For a randomized policy, one evaluates expected total movement over the algorithm's private random choices. An oblivious request sequence is chosen independently of those random choices. This is distinct from a fully adaptive adversary allowed to select new requests after observing the policy's random outcomes.
What is known
The protected Family 110 catalogue identifies two manuscripts: Squared-logarithmic randomized k-server on arbitrary metrics and Uniform computation of the squared-logarithmic k-server bound.
The pinned publisher overview claims a randomized competitive guarantee of order
for every metric space and every finite oblivious request sequence, matching the stated worst-case lower-bound order. The guarantee is described as coming from one policy, not one separately tailored to each request sequence. The claimed scope extends to infinite, unbounded metric spaces.
The companion manuscript addresses constructive computation on finite rational metrics. The overview asserts polynomial preprocessing and per-request bit cost in the input length and \(\log(t+1)\) at request index \(t\), with a finite instance-dependent additive movement constant. Such an additive allowance is not itself part of the multiplicative competitive ratio and must be retained in any faithful statement.
Neither claim automatically covers adaptive adversaries, arbitrary real-number metric encodings in a finite Turing-machine model, or finite worst-case movement for unbounded request sequences without the stated competitive comparison.
GCL verification state
The source lock is openai/math@1581d4cbdd69a0faf34b2089614fe2a814316a6a. Both manuscript paths appear in the protected catalogue. The pinned overview supplies the asymptotic ratio, oblivious-adversary scope, arbitrary-metric existence claim and finite-rational implementation bounds.
This editorial pass has not checked the proof of the competitive estimate, the precise randomized policy and state information, whether randomization or expectations satisfy all quantifiers, the lower bound to which “optimal order” refers, or the bit-complexity and additive-cost calculations. No Family 110-specific Lean receipt, critical proof audit, Comparator determination, or MATHCERT certificate is asserted.
What remains
Read both pinned PDFs and extract the exact competitive inequality, including the order of quantifiers over metric spaces, initial configurations, request sequences and random coins, and any additive constants. Determine the full admissible class of metrics and whether zero-distance identifications or infinite pairwise distances are excluded.
Reconstruct the online policy, its measurability and implementation assumptions on arbitrary metric spaces, and its comparison with the worst-case lower bound. Separately audit the finite rational-metric algorithm: input encoding, preprocessing costs, arithmetic precision, per-request time bound, and the instance-dependent additive movement term.
Complete source-critical review and mathematical Markdown/MkDocs regression, followed by protected merge/readback. Documentary admission does not certify the competitive guarantee.
Sources and claim boundaries
- Pinned squared-logarithmic randomized k-server manuscript.
- Pinned uniform-computation manuscript.
- Pinned OAI-26 overview, Family 110.
- GCL editorial assignment.
Boundary: NO_CERTIFICATION. Both algorithmic claims await independent mathematical verification.
Indexed primary manuscript paths:
- Squared-logarithmic randomized k-server on arbitrary metrics —
preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf - Uniform computation of the squared-logarithmic k-server bound —
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