@inproceedings{9c283bb3b55047c3879b7182f0356de1,
title = "Tight bounds for double coverage against weak adversaries",
abstract = "We study the Double Coverage (DC) algorithm for the k-server problem in the (h, k)-setting, i.e. when DC with k servers is compared against an offline optimum algorithm with h≤k h≤k servers. It is well-known that DC is k-competitive for h=k h=k . We prove that even if k>h k>h the competitive ratio of DC does not improve; in fact, it increases up to h+1 h+1 as k grows. In particular, we show matching upper and lower bounds of k(h+1)k+1 k(h+1)k+1 on the competitive ratio of DC on any tree metric. ",
author = "N. Bansal and M. Elias and L. Jez and G. Koumoutsos and K. Pruhs",
year = "2015",
doi = "10.1007/978-3-319-28684-6_5",
language = "English",
isbn = "978-3-319-28683-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "47--58",
editor = "L. Sanit{\`a} and M. Skutella",
booktitle = "Approximation and Online Algorithms",
}