Lower Bounds for Randomized k -Server and Motion-Planning Algorithms
Howard J. Karloff, Yuval Rabani, Yiftach Ravid · SIAM Journal on Computing · 1994
In this paper, the authors prove lower bounds on the competitive ratio of randomized algorithms for two on-line problems: the k-server problem, suggested by Manasse, McGeoch, and Sleator [Competitive lgorithms for on-line problems, J. Algorithms, 11 (1990), pp. 208–230], and an on-line motion-planning problem due to Papadimitriou and Yannakakis [Shortest paths without a map, Lecture Notes in Comput. Sci. 372, Springer-Verlag, New York, 1989, pp. 610–620]. The authors prove, against an oblivious adversary, 1. an $\Omega \log k$ lower bound on the competitive ratio of any randomized on-line k-server algorithm in any sufficiently large metric space, 2. an $\Omega (\log \log k)$ lower bound on the competitive ratio of any randomized on-line k-server algorithm in any metric space with at least $k + 1$ points, and 3. an $\Omega (\log \log n)$ lower bound on the competitive ratio of any on-line motion-planning algorithm for a scene with n obstacles. Previously, no superconstant lower bound on the competitive ratio of randomized on-line algorithms was known for any of these problems.