Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9657016 | Journal of Algorithms | 2005 | 11 Pages |
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. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, 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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yair Bartal, Manor Mendel,