Name
Abstract | ||
|---|---|---|
We define a natural generalization of the prominent k-server problem, the k-resource problem. It occurs in a metric space with some integer demands given at its points. The demands may vary with time, but the total demand may never exceed k. An online algorithm has k servers at its disposal and its goal is to satisfy demands by moving servers, while minimizing the cost of their transport. We show asymptotically tight bounds on the competitive ratio of the k-resource problem in the uniform metric space of n points: we prove that the optimal competitive ratios are between min{k,n-1} and min{k,2(n-1)} for deterministic algorithms and between min{H"k,H"n"-"1} and min{H"k,2@?H"n"-"1} for randomized ones. This extends known results for k-server in such spaces to the more general setting of k-resource. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.tcs.2012.06.026 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
k-resource problem,deterministic algorithm,competitive ratio,prominent k-server problem,asymptotically tight bound,metric space,general setting,uniform metric space,k server,optimal competitive ratio | Journal | 459, |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
17 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Bienkowski | 1 | 254 | 27.18 |
| Jarosaw Kutyowski | 2 | 20 | 1.45 |