Name
Abstract | ||
|---|---|---|
We study the resource augmented version of the k-server problem, also known as the k-server problem against weak adversaries or the (h,k)-server problem. In this setting, an online algorithm using k servers is compared to an offline algorithm using h servers, where h ≤ k. For uniform metrics, it has been known since the seminal work of Sleator and Tarjan (1985) that for any є>0, the competitive ratio drops to a constant if k=(1+є) · h. This result was later generalized to weighted stars (Young 1994) and trees of bounded depth (Bansal et al. 2017). The main open problem for this setting is whether a similar phenomenon occurs on general metrics. We resolve this question negatively. With a simple recursive construction, we show that the competitive ratio is at least Ω(loglogh), even as k→∞. Our lower bound holds for both deterministic and randomized algorithms. It also disproves the existence of a competitive algorithm for the infinite server problem on general metrics.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3357713.3384306 | STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing
Chicago
IL
USA
June, 2020 |
Keywords | DocType | ISSN |
online algorithms, k-server, weak adversaries, resource augmentation | Conference | 0737-8017 |
ISBN | Citations | PageRank |
978-1-4503-6979-4 | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marcin Bienkowski | 1 | 254 | 27.18 |
| Jaroslaw Byrka | 2 | 523 | 31.45 |
| Coester Christian | 3 | 0 | 0.68 |
| Lukasz Jez | 4 | 61 | 11.93 |