×

Tight bounds for double coverage against weak adversaries. (English) Zbl 1390.68767

Summary: 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\leq 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 \(\frac {k(h+1)}{k+1}\) on the competitive ratio of DC on any tree metric.

MSC:

68W27 Online algorithms; streaming algorithms
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bartal, Y., Koutsoupias, E.: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci 324(2-3), 337-345 (2004) · Zbl 1072.68014 · doi:10.1016/j.tcs.2004.06.001
[2] Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press (1998) · Zbl 0931.68015
[3] Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discrete Math. 4(2), 172-181 (1991) · Zbl 0726.68031 · doi:10.1137/0404017
[4] Chrobak, M., Larmore, L.L.: An optimal on-line algorithm for k-servers on trees. SIAM J. Comput. 20(1), 144-148 (1991). doi:10.1137/0220008 · Zbl 0716.68038
[5] Chrobak, M., Larmore, L.L.: The server problem and on-line games. In: On-line Algorithms, volume 7 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 11-64. AMS/ACM (1992) · Zbl 0800.68489
[6] Koutsoupias, E.: Weak adversaries for the k-server problem. In: Proc. of the 40th Symp. on Foundations of Computer Science (FOCS), pp. 444-449 (1999) · Zbl 1072.68014
[7] Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971-983 (1995) · Zbl 0885.68075 · doi:10.1145/210118.210128
[8] Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. ACM 11(2), 208-230 (1990) · Zbl 0705.68023
[9] Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202-208 (1985). doi:10.1145/2786.2793 · Zbl 1072.68014
[10] Young, N.E.: The k-server dual and loose competitiveness for paging. Algorithmica 11(6), 525-541 (1994). doi:10.1007/BF01189992 · Zbl 0885.68075
[11] Young, N.E.: On-line file caching. Algorithmica 33(3), 371-383 (2002). Journal version of [1998] doi:10.1007/s00453-001-0124-5 · Zbl 0994.68182
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.