2018-02-01
Tight bounds for Double Coverage against weak adversaries
Publication
Publication
Theory of Computing Systems , Volume 62 - Issue 2 p. 349- 365
We study the Double Coverage (DC) algorithm for the k-server problem in tree metrics in the (h,k)-setting, i.e., when DC with k servers is compared against an offline optimum algorithm with h ≤ k servers. It is well-known that in such metric spaces DC is k-competitive (and thus optimal) for h = k. We prove that even if k > h the competitive ratio of DC does not improve; in fact, it increases slightly as k grows, tending to h + 1. Specifically, we give matching upper and lower bounds of (k(h+1)) / (k+1) on the competitive ratio of DC on any tree metric.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/s00224-016-9703-3 | |
| Theory of Computing Systems | |
| Organisation | Networks and Optimization |
|
Bansal, N., Eliáš, M., Jeż, Ł., Koumoutsos, G., & Pruhs, K. (2018). Tight bounds for Double Coverage against weak adversaries. Theory of Computing Systems, 62(2), 349–365. doi:10.1007/s00224-016-9703-3 |
|
