×

Competitive \(k\)-server algorithms. (English) Zbl 0806.68056

Summary: We give deterministic competitive \(k\)-server algorithms for all \(k\) and all metric spaces. This settles the \(k\)-server conjecture up to the competitive ratio. The best previous result for general metric spaces was a three-server randomized competitive algorithm and a non-constructive proof that a deterministic three-server competitive algorithm exists. The competitive ratio we can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open.

MSC:

68Q25 Analysis of algorithms and problem complexity
68P10 Searching and sorting
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ben-David, S.; Borodin, A.; Karp, R. M.; Tardos, G.; Wigderson, A., On the power of randomization in on-line algorithms, (Proceedings, 22nd Annu. ACM Symp. on Theory of Computing. Proceedings, 22nd Annu. ACM Symp. on Theory of Computing, May (1990)), 379-386
[2] Berman, P.; Karloff, H. J.; Tardos, G., A competitive three-server algorithm, (Proceedings, 1st Annu. ACM-SIAM Symp. on Discrete Algorithms. Proceedings, 1st Annu. ACM-SIAM Symp. on Discrete Algorithms, January (1990)), 280-290 · Zbl 0800.68452
[3] Borodin, A.; Linial, N.; Saks, M., An optimal on-line algorithm for metrical task systems, (Proceedings, 19th Annu. ACM Symp. on Theory of Computing. Proceedings, 19th Annu. ACM Symp. on Theory of Computing, May (1987)), 373-382
[4] Baeza-Yates, R. A.; Culberson, J. C.; Rawlins, G. J.E., Searching with Uncertaincy, (Technical report (1987), University of Waterloo: University of Waterloo Englewood Cliffs, NJ), October
[5] Coppersmith, D.; Doyle, P.; Raghaven, P.; Snir, M., Random walks on weighted graphs and applications to on-line algorithms, (Proceedings, 22nd Annu. ACM Symp. on Theory of Computing. Proceedings, 22nd Annu. ACM Symp. on Theory of Computing, May (1990)), 369-378
[6] Chrobak, M.; Karloff, H. J.; Payne, T.; Vishwanathan, S., New results on server problem, SIAM J. Discrete Math., 4, No. 2, 172-181 (1991) · Zbl 0726.68031
[7] Chrobak, M.; Larmore, L., An optimal on-line algorithm for the server problem on trees, SIAM J. Comput., 20, 144-148 (1991) · Zbl 0716.68038
[8] Chrobak, M.; Larmore, L., On fast algorithm for two servers, (Proceedings, Mathematical Foundations of Computer Science, Banská Bystrica, 1990. Proceedings, Mathematical Foundations of Computer Science, Banská Bystrica, 1990, J. Algorithms, 12 (1991)), 607-614 · Zbl 0767.68054
[9] Fiat, A.; Foster, D. P.; Karloff, H. J.; Rabani, Y.; Ravid, Y.; Vishwanathan, S., Competitive algorithms for layered graph traversal, (Proceedings, 32nd Annu. Symp. on Foundations of Comput. Sci.. Proceedings, 32nd Annu. Symp. on Foundations of Comput. Sci., October (1991)), 288-297
[10] Fiat, A.; Karp, R. M.; Luby, M.; McGeoch, L. A.; Sleator, D. D.; Young, N. E., Competitive paging algorithms, J. Algorithms, 12, 685-699 (1991) · Zbl 0753.68018
[12] Grove, E., The harmonic \(k\)-server algorithm is competitive, (Proceedings, 23nd Annu. ACM Symp. on Theory of Computing. Proceedings, 23nd Annu. ACM Symp. on Theory of Computing, May (1991)), 260-266
[13] Irani, S.; Rubinfeld, R., A competitive 2-server algorithm, Inform. Process. Lett., 39, 85-91 (1991) · Zbl 0736.68043
[14] Karp, R. M., A randomized \((n + 1)k\) competitive algorithm on the graph (1989), personal communication
[15] Karlin, A. R.; Manasse, M. S.; McGeoch, L. A.; Owicki, S., Competitive randomized algorithms for non-uniform problems, (Proceedings, 1st Annu. ACM-SIAM Symp. on Discrete Algorithms. Proceedings, 1st Annu. ACM-SIAM Symp. on Discrete Algorithms, January (1990)), 301-309 · Zbl 0800.68456
[16] Karlin, A. R.; Manasse, M. S.; Rudolph, L.; Sleator, D. D., Competitive Snoopy caching, Algorithmica, 3, 1, 79-119 (1988) · Zbl 0645.68034
[17] (Proceedings 20th Annu. ACM Symp. on Theory of Coputing. Proceedings 20th Annu. ACM Symp. on Theory of Coputing, May (1988)), 322-333
[19] Papadimitriou, C. H.; Yannakakis, M., Shortest paths without a map, (Proceedings, 16th ICALP. Proceedings, 16th ICALP, July (1989)), 610-620
[20] Raghavan, P., Lecture Notes on Randomized Algorithms, (Technical report (1990), IBM), September
[21] (Lecture Notes in Computer Science, Vol. 372 (1992), Springer-Verlag: Springer-Verlag Yorktown)
[22] Sleator, D. D.; Tarjan, R. E., Amortized efficiency of list update and paging rules, Commun. ACM, 28, 202-208 (1985)
[23] Turpin, G., Recent Work on the Server Problem, (Master’s thesis (1989), University of Toronto: University of Toronto New York/Berlin)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.