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. 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 this metric space. A sequence of requests is presented, each request is associated with a point in the metric space and must be served by moving one of the k servers to the request point. The cost of an algorithm for serving a sequence of requests is the total distance traveled by the servers. The problem is formulated as an online problem, in which the servers algorithm must make the movement decision without the knowledge of future requests. Denote by cost A (σ) the cost of an algorithm A for serving the request σ (in case A is randomized algorithm, this is a random variable), and by cost opt (σ) the minimal cost for serving σ. As customary for online algorithms, we measure their performance using the competitive ratio. A randomized online algorithm A is called r-competitive if exists some C such that for any task sequence σ, [cost A (σ)] ≤ r cost opt (σ) + C. The randomized (resp. deterministic) competitive ratio is the infimum over r for which there exists a randomized (resp. deterministic) r-competitive algorithm. The k-server problem attracted much research,
One of the well studied online algorithm for assigning resources to users is the kserver problem REF where, the servers handle request once for each client.
Randomized k-server algorithms for growth-rate bounded graphs
SODA '04
Mathematics Computer Science