Randomized k-server on arbitrary metrics: a competitive ratio polylogarithmic in k, of optimal order log^2 k

Theorem 1.1: an absolute $C$ such that for every $k\ge2$, every metric space with at least $k+1$ points and every start, one randomized online policy has $\mathbb E\,\mathrm{cost}\le C(\log(k+1))^2\mathrm{OPT}+B$ on every finite oblivious request sequence; $B$ depends on the instance and is 0 for distinct starting positions. With Bubeck-Coester-Rabani this is the sharp worst-case order. The policy is not claimed efficient; the companion gives polynomial-time preprocessing and per-request cost on finite rational metrics, with a possibly enormous additive constant. It does not determine the optimal ratio on each individual metric, nor the deterministic ratio.

Theorem 1.1: an absolute $C$ such that for every $k\ge2$, every metric space with at least $k+1$ points and every start, one randomized online policy has $\mathbb E\,\mathrm{cost}\le C(\log(k+1))^2\mathrm{OPT}+B$ on every finite oblivious request sequence; $B$ depends on the instance and is 0 for distinct starting positions. With Bubeck-Coester-Rabani this is the sharp worst-case order. The policy is not claimed efficient; the companion gives polynomial-time preprocessing and per-request cost on finite rational metrics, with a possibly enormous additive constant. It does not determine the optimal ratio on each individual metric, nor the deterministic ratio.