Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10333164 | Journal of Discrete Algorithms | 2009 | 9 Pages |
Abstract
We study the randomized k-server problem on metric spaces consisting of widely separated subspaces. We give a method which extends existing algorithms to larger spaces with the growth rate of the competitive quotients being at most O(logk). This method yields o(k)-competitive algorithms solving the randomized k-server problem for some special underlying metric spaces, e.g. HSTs of “small” height (but unbounded degree). HSTs are important tools for probabilistic approximation of metric spaces.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Judit Nagy-György,