TY - JOUR
T1 - Tight bounds for double coverage against weak adversaries
AU - Bansal, N.
AU - Elias, M.
AU - Jez, L.
AU - Koumoutsos, G.
AU - Pruhs, K.
PY - 2018/2/1
Y1 - 2018/2/1
N2 - 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.
AB - 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.
KW - Double coverage
KW - Resource augmentation
KW - Weak adversaries
KW - k-server
UR - http://www.scopus.com/inward/record.url?scp=84984868278&partnerID=8YFLogxK
U2 - 10.1007/s00224-016-9703-3
DO - 10.1007/s00224-016-9703-3
M3 - Article
SN - 1432-4350
VL - 62
SP - 349
EP - 365
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 2
ER -