Tight bounds for double coverage against weak adversaries

N. Bansal; M. Elias; L. Jez; G. Koumoutsos; K. Pruhs

doi:10.1007/978-3-319-28684-6_5

Tight bounds for double coverage against weak adversaries

N. Bansal, M. Elias, L. Jez, G. Koumoutsos, K. Pruhs

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

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.

Original language	English
Title of host publication	Approximation and Online Algorithms
Subtitle of host publication	13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers
Editors	L. Sanità, M. Skutella
Place of Publication	Dordrecht
Publisher	Springer
Pages	47-58
ISBN (Electronic)	978-3-319-28684-6
ISBN (Print)	978-3-319-28683-9
DOIs	https://doi.org/10.1007/978-3-319-28684-6_5
Publication status	Published - 2015

Publication series

Name	Lecture Notes in Computer Science
Volume	9499

Access to Document

10.1007/978-3-319-28684-6_5

Cite this

Bansal, N., Elias, M., Jez, L., Koumoutsos, G., & Pruhs, K. (2015). Tight bounds for double coverage against weak adversaries. In L. Sanità, & M. Skutella (Eds.), Approximation and Online Algorithms: 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers (pp. 47-58). (Lecture Notes in Computer Science; Vol. 9499). Springer. https://doi.org/10.1007/978-3-319-28684-6_5

@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",

}

Bansal, N, Elias, M, Jez, L, Koumoutsos, G & Pruhs, K 2015, Tight bounds for double coverage against weak adversaries. in L Sanità & M Skutella (eds), Approximation and Online Algorithms: 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers. Lecture Notes in Computer Science, vol. 9499, Springer, Dordrecht, pp. 47-58. https://doi.org/10.1007/978-3-319-28684-6_5

Tight bounds for double coverage against weak adversaries. / Bansal, N.; Elias, M.; Jez, L. et al.
Approximation and Online Algorithms: 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers. ed. / L. Sanità; M. Skutella. Dordrecht: Springer, 2015. p. 47-58 (Lecture Notes in Computer Science; Vol. 9499).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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 - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-28684-6_5

DO - 10.1007/978-3-319-28684-6_5

M3 - Conference contribution

SN - 978-3-319-28683-9

T3 - Lecture Notes in Computer Science

SP - 47

EP - 58

BT - Approximation and Online Algorithms

A2 - Sanità, L.

A2 - Skutella, M.

PB - Springer

CY - Dordrecht

ER -

Bansal N, Elias M, Jez L, Koumoutsos G, Pruhs K. Tight bounds for double coverage against weak adversaries. In Sanità L, Skutella M, editors, Approximation and Online Algorithms: 13th International Workshop, WAOA 2015, Patras, Greece, September 17-18, 2015. Revised Selected Papers. Dordrecht: Springer. 2015. p. 47-58. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-28684-6_5

Tight bounds for double coverage against weak adversaries

Abstract

Publication series

Access to Document

Fingerprint

Cite this