@inbook {IOPORT.01256655,
    author       = {Blum, Avrim and Karloff, Howard and Rabani, Yuval and Saks, Michael},
    title        = {A decomposition theorem and bounds for randomized server problems.},
    year         = {1992},
    booktitle    = {33rd annual symposium on Foundations of computer science (FOCS). Proceedings, Pittsburgh, PA, USA, October 24--27, 1992},
    pages        = {197-207},
    publisher    = {Washington, DC: IEEE Computer Society Press},
    abstract     = {Summary: We prove a lower bound of $\Omega(\sqrt {\log k/ \log \log k})$ 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 (\log\log k)$ for arbitrary metric spaces, more closely approaching the conjectured lower bound of $\Omega(\log k)$. We also prove a lower bound of $\Omega({\log k \over \log\log k})$ for the server problem on $k+1$ equally-spaced points on a line, which corresponds to some natural motion-planning problems. Our results are deduced from a general decomposition theorem for a simpler version of both the $k$-server and the metrical task system problems, which we call the ``pursuit-evasion game''. We show that if a metric space ${\cal M}$ can be decomposed into two spaces ${\cal M}_L$ and ${\cal M}_R$, both very far away from each other, then the randomized competitive ratio for this game on ${\cal M}$ can be expressed nearly exactly in terms of the ratios on each of the two subspaces. This provides a natural way of analyzing the competitive ratio of a complex space made up of several regions in terms of the ratios of its components.},
    identifier   = {01256655},
}