×

On the power of randomization in on-line algorithms. (English) Zbl 0784.68038

Summary: Against in adaptive adversary, we show that the power of randomization in on-line algorithms is severely limited! We prove the existence of an efficient “simulation” of randomized on-line algorithms by deterministic ones, which is best possible in general. The proof of the upper bound is existential. We deal with the issue of computing the efficient deterministic algorithm, and show that this is possible in very general cases.

MSC:

68Q25 Analysis of algorithms and problem complexity
91A80 Applications of game theory
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] P. Berman, H. J. Karloff, and G. Tardos. A competitive three-server algorithm. Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 280-290, Jan. 1990. · Zbl 0800.68452
[2] A. Borodin, N. Linial, and M. Saks. An optimal on-line algorithm for metrical task systems. Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pages 373-382, New York City, May 1987. · Zbl 0799.68035
[3] A. Borodin, N. Linial, and M. Saks. An optimal on-line algorithm for metrical task systems.J. Assoc. Comput. Mach., 39(4):743-763, 1992. · Zbl 0799.68035
[4] M. Chrobak, H. Karloff, T. Payne, and S. Vishwanathan. New results on server problems.Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pages 291-300, Jan. 1990. To appear inSIAM J. Discrete Math. · Zbl 0800.68460
[5] D. Coppersmith, P. Doyle, P. Raghavan, and M. Snir. Random walks on weighted graphs, and applications to on-line algorithms.Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 369-378, Baltimore, MD, May 1990. · Zbl 0785.68071
[6] X. Deng, and S. Mahajan. Randomization vs. computability in on-line problems.Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 289-298, New Orleans, LA, May 1991.
[7] A. Fiat, R. M. Karp, M. Luby, L. A. McGeoch, D. D. Sleator, and N. E. Young. Competitive paging algorithms.J. Algorithms, 12:685-699, 1991. · Zbl 0753.68018
[8] A. Fiat, Y. Rabani, and Y. Ravid. Competitive K-server algorithms.Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 454-463, St. Louis, MO, Oct. 1990. · Zbl 0806.68056
[9] D. Gale and F. M. Stewart.Infinite games with perfect information. In W. H. Kuhn and A. W. Tucker, editors,Contributions to the Theory of Games, Vol. II, pages 245-266. Annals of Mathematics Studies, 28, Princeton University Press, Princeton, NJ, 1953. · Zbl 0050.14305
[10] E. Grove. The harmonick-server algorithm is competitive.Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 260-266, New Orleans, LA, May 1991.
[11] A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching.Algorithmica, 3(1):79-119, 1988. · Zbl 0645.68034
[12] M. S. Manasse, L. A. McGeoch, and D. D. Sleator. Competitive algorithms for on-line problems.J. Algorithms, 11:208-230, 1990. · Zbl 0705.68023
[13] D. A. Martin. Borel determinacy.Ann. of Math., 102:363-371, 1975. · Zbl 0336.02049
[14] L. A. McGeoch and D. D. Sleator. A strongly competitive randomized paging algorithm.Algorithmica, 6(6):816-825, 1991. · Zbl 0731.68040
[15] P. Raghavan and M. Snir. Memory vs. randomization in on-line algorithms. In ICALP, Italy, July 1989.Proceedings of the 16th ICALP, pages 687-703. LNCS, 372, Springer-Verlag, Berlin, 1990.
[16] P. Raghavan and M. Snir. Memory vs. randomization in on-line algorithms. Revised version of the ICALP paper. Submitted toJ. Assoc. Comput. Mach.
[17] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules.Comm. ACM, 28(2):202-208, 1985.
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.