Randomized k-server algorithms for growth-rate bounded graphs
Yair Bartal, Manor Mendel · 2004
Abstract The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k) competitive ratios. This goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction obtaining o(k) competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k. Prior to this work no result of this type was known beyond results for specific metric spaces. 1 Introduction The k-server problem, defined by Manasse, McGeoch,and Sleator [18], consists of an n-point metric space,and k mobile servers (k < n) residing in points of thismetric space. A sequence of requests is presented, each