A decomposition theorem and bounds for randomized server problems
Avrim L. Blum, Howard J. Karloff, Yuval Rabani, Michael Saks · 1992
The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems.>