LOWER BOUNDS FOR RANDOMIZED K-SERVER AND MOTION-PLANNING ALGORITHMS

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 algorithms 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.