|
Optimal-order randomized $k$-server on arbitrary metrics
at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages
LOADING...
0%
thinking... about 3 hours remaining
GAME #110
Optimal-order randomized $k$-server on arbitrary metrics
2 levels of pure algorithms, speed!
PLAY
LEAN
VERIFIED
If this game doesn't work on your computer, go here for help. (Lean version available!)expertly designed by an internal OpenAI model
| >>> How to Play <<< |
| Optimal-order randomized k-server on arbitrary metrics. 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. |
| >>> Level Select <<< |
|
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.
| |
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.
|
|