Competitive randomized algorithms for nonuniform problems. (English) Zbl 0806.68053

Summary: Competitive analysis is concerned with comparing the performance of on- line algorithms with that of optimal off-line algorithms. In some cases randomization can lead to algorithms with improved performance ratios on worst-case sequences. In this paper we present new randomized on-line algorithms for snoopy caching and the spin-block problem. These algorithms achieve competitive ratios approaching \(e/(e-1) \approx 1.58\) against an oblivious adversary. These ratios are optimal and are a surprising improvement over the best possible ratio in the deterministic case, which is 2. We also consider the situation when the request sequences for these problems are generated according to an unknown probability distribution. In this case we show that deterministic algorithms that adapt to the observed request statistics also have competitive factors approaching \(e/(e - 1)\). Finally, we obtain randomized algorithms for the 2-server problem on a class of isosceles triangles. These algorithms are optimal against an oblivious adversary and have competitive ratios that approach \(e/(e - 1)\). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.


68W15 Distributed algorithms


Full Text: DOI


[1] Ben-David, S., Borodin, A., Karp, R., Tardos, G., and Wigderson, A. On the power of randomization in on-line algorithms.Algorithmica,11:2-14, 1994. · Zbl 0784.68038
[2] Berman, P., Karloff, H., and Tardos, G. A competitive three-server algorithm.Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, 1990, pages 280-290. · Zbl 0800.68452
[3] Borodin, A., Linial, N., and Saks, M. An optimal online algorithm for metrical task systems.Proceedings of the 19th Annual ACM Symposium on Theory of Computing, New York, 1987, pages 373-382.
[4] Borodin, A., Linial, N., and Saks, M. An optimal on-line algorithm for metrical task systems.J. Assoc. Comput. Mach.,39(4):745-763, 1992. · Zbl 0799.68035
[5] Chrobak, M., Karloff, H., Payne, T., and Vishwanathan, S. New results on server problems.SIAM J. Discrete Math.,4(2): 172-181, 1991. · Zbl 0726.68031
[6] Chrobak, M. and Larmore, L. L. A new approach to the server problem.SIAM J. Discrete Math.,4(3):323-328, 1991. · Zbl 0737.68041
[7] Chrobak, M. and Larmore, L. L. An optimal on-line algorithm fork servers on trees.SIAM J. Comput.,20(1): 144-148, 1991. · Zbl 0716.68038
[8] Coppersmith, D., Doyle, P., Raghavan, P., and Snir, M. Random Walks on Weighted Graphs, and Applications to On-Line Algorithms.J. Assoc. Comput. Mach.,40(3):421-453, 1993. · Zbl 0785.68071
[9] Eggers, S. J., and Katz, R. H. Evaluating the performance of four snooping cache coherency protocols.Proceedings of the 16th Annual International Symposium on Computer Architecture, 1989.
[10] Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., and Young, N. E. Competitive paging algorithms.J. Algorithms,12(4):685-699, 1991. · Zbl 0753.68018
[11] Fiat, A., Rabani, Y., and Ravid, Y. Competitivek-server algorithms.J. Comput. System Sci., to appear. · Zbl 0806.68056
[12] Grove, E. F. The harmonic onlinek-server algorithm is competitive.Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, 1991, pages 260-266.
[13] Irani, S., and Rubinfeld, R. A competitive 2-server algorithm.Inform. Process. Lett.,39(2): 85-91, 1991. · Zbl 0736.68043
[14] Karlin, A. R., Manasse, M. S., Rudolph, L., and Sleator, D. D. Competitive snoopy caching.Algorithmica,3(1): 79-119, 1988. · Zbl 0645.68034
[15] Karloff, H., Rabani, Y., and Ravid, Y. Lower bounds for randomizedk-server and motionplanning algorithms.SIAM J. Comput., to appear, 1994. · Zbl 0804.68066
[16] Manasse, M. S., McGeoch, L. A., and Sleator, D. D. Competitive algorithms for server problems.J. Algorithms,11(2):208-230, 1990. · Zbl 0705.68023
[17] McGeoch, L. A. Algorithms for Two Graph Problems. Ph.D. thesis, Carnegie Mellon University, 1987.
[18] McGeoch, L. A., and Sleator, D. D. A strongly competitive randomized paging algorithm.Algorithmica,6(6):816-825, 1991. · Zbl 0731.68040
[19] Raghavan, P., and Snir, M. Memory Versus Randomization in On-line Algorithms. IBM Research Report, 1990. Submitted for publication.
[20] Sleator, D. D., and Tarjan, R. E. Amortized efficiency of list update and paging rules.Comm.
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.