Abstract
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 approachinge/(e−1) ≈ 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 approachinge/(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 approache/(e−1). This compares with the ratio of 3/2 that can be achieved on an equilateral triangle.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
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.
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.
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.
Chrobak, M., Karloff, H., Payne, T., and Vishwanathan, S. New results on server problems.SIAM J. Discrete Math.,4(2): 172–181, 1991.
Chrobak, M. and Larmore, L. L. A new approach to the server problem.SIAM J. Discrete Math.,4(3):323–328, 1991.
Chrobak, M. and Larmore, L. L. An optimal on-line algorithm fork servers on trees.SIAM J. Comput.,20(1): 144–148, 1991.
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.
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.
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.
Fiat, A., Rabani, Y., and Ravid, Y. Competitivek-server algorithms.J. Comput. System Sci., to appear.
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.
Irani, S., and Rubinfeld, R. A competitive 2-server algorithm.Inform. Process. Lett.,39(2): 85–91, 1991.
Karlin, A. R., Manasse, M. S., Rudolph, L., and Sleator, D. D. Competitive snoopy caching.Algorithmica,3(1): 79–119, 1988.
Karloff, H., Rabani, Y., and Ravid, Y. Lower bounds for randomizedk-server and motionplanning algorithms.SIAM J. Comput., to appear, 1994.
Manasse, M. S., McGeoch, L. A., and Sleator, D. D. Competitive algorithms for server problems.J. Algorithms,11(2):208–230, 1990.
McGeoch, L. A. Algorithms for Two Graph Problems. Ph.D. thesis, Carnegie Mellon University, 1987.
McGeoch, L. A., and Sleator, D. D. A strongly competitive randomized paging algorithm.Algorithmica,6(6):816–825, 1991.
Raghavan, P., and Snir, M. Memory Versus Randomization in On-line Algorithms. IBM Research Report, 1990. Submitted for publication.
Sleator, D. D., and Tarjan, R. E. Amortized efficiency of list update and paging rules.Comm.
Author information
Authors and Affiliations
Additional information
Communicated by Prabhakar Raghavan.
Supported in part by the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), an NSF Science and Technology Center funded under NSF Contract STC-88-09648 and supported by the New Jersey Commission on Science and Technology.
Rights and permissions
About this article
Cite this article
Karlin, A.R., Manasse, M.S., McGeoch, L.A. et al. Competitive randomized algorithms for nonuniform problems. Algorithmica 11, 542–571 (1994). https://doi.org/10.1007/BF01189993
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01189993