Abstract
We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constantd. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
N. Alon, R. M. Karp, D. Peleg, and D. West. A graph-theoretic game and its application to thek-server problem.Proc. DIMACS Workshop on On-line Algorithms, pages 1–10. American Mathematical Society, Providence, RI, 1991.
S. Ben-David, A. Borodin, R. M. Karp, G. Tárdos, and A. Wigderson. On the power of randomization in on-line algorithms.Proc. 20th ACM Symp. on Theory of Computing, pages 379–386, 1990.
J. L. Bentley, K. L. Clarkson, and D. B. Levine. Fast linear expected-time algorithms for computing maxima and convex hulls.Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pages 179–187, 1990.
J. L. Bentley and C. C. McGeoch. Amortized analyses of self-organizing sequential search heuristics.Comm. ACM, 28(4):404–411, 1985.
J. L. Bentley, D. D. Sleator, R. E. Tarjan, and V. Wei. A locally adaptive data compression scheme.Comm. ACM, 29(4):320–330, 1986.
D. L. Black and D. D. Sleator. Competitive algorithms for replication and migration problems. Technical Report CMU-CS-89-201, Department of Computer Science, Carnegie-Mellon University, 1989.
A. Borodin, N. Linial, and M. Saks. An optimal on-line algorithm for metrical task systems.Proc. 19th ACM Symp. on Theory of Computing, pages 373–382, 1987.
P. J. Burville and J. F. C. Kingman. On a model for storage and search.J. Appl. Probab., 10:697–701, 1973.
M. Chrobak and L. Larmore. On fast algorithms for two servers.J. Algorithms, 12:607–614, 1991.
M. Chrobak, L. L. Larmore, N. Reingold, and J. Westbrook. Optimal multiprocessor migration algorithms using work functions. Technical Report YALEU/DCS/TR-897, Department of Computer Science, Yale University, 1991.
S. D. Conte and C. de Boor.Elementary Numerical Analysis, An Algorithmic Approach, 3rd edn. McGraw-Hill, New York, 1980.
D. Coppersmith, P. Doyle, P. Raghavan, and M. Snir. Random walks on weighted graphs, and applications to on-line algorithms.Proc. 20th ACM Symp. on Theory of Computing, pages 369–377, 1990.
A. Fiat, R. Karp, M. Luby, L. McGeoch, D. D. Sleator, and N. Young. On competitive algorithms for paging problems.J. Algorithms, 12:685–699, 1991.
M. J. Golin. Ph.D. thesis, Department of Computer Science, Princeton University, 1990. Technical Report CS-TR-266-90.
W. J. Hendricks. An account of self-organizing systems.SIAM J. Comput., 5(4):715–723, 1976.
S. Irani. Two results on the list update problem.Inform. Process. Lett., 38:301–306, 1991.
S. Irani, N. Reingold, J. Westbrook, and D. D. Sleator. Randomized algorithms for the list update problem.Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, pages 251–260, 1991.
A. R. Karlin, M. S. Manasse, L. A. McGeoch, and S. Owicki. Competitive randomized algorithms for non-uniform problems.Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, 1990.
A. Karlin, M. Manasse, L. Rudolph, and D. Sleator. Competitive snoopy caching.Algorithmica, 3(1):79–119, 1988.
M. Manasse, L. A. McGeoch, and D. Sleator. Competitive algorithms for on-line problems.Proc. 20th ACM Symp. on Theory of Computing, pages 322–333, 1988.
J. McCabe. On serial files with relocatable records.Oper. Res., 13:609–618, 1965.
P. Raghavan and M. Snir. Memory versus randomization in on-line algorithms. Research Report RC 15622 (No. 69444), IBM T. J. Watson Reseach Center, 1990.
N. Reingold and J. Westbrook. Optimum off-line algorithms for the list update problem. Technical Report YALEU/DCS/TR-805, Yale University, 1990.
R. Rivest. On self-organizing sequential search heuristics.Comm. ACM, 19(2):63–67, 1976.
D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules.Comm. ACM, 28(2):202–208, 1985.
J. Westbrook. Randomized algorithms for multiprocessor page migration.Proc. DIMACS Workshop on On-Line Algorithms, pages 135–150. American Mathematical Society, Providence, RI, 1991.
Author information
Authors and Affiliations
Additional information
Communicated by Prabhakar Raghavan.
A preliminary version of these results appeared in a joint paper with S. Irani in theProceedings of the 2nd Symposium on Discrete Algorithms, 1991 [17].
This research was partially supported by NSF Grants CCR-8808949 and CCR-8958528.
This research was partially supported by NSF Grant CCR-9009753.
This research was supported in part by the National Science Foundation under Grant CCR-8658139, by DIMACS, a National Science Foundation Science and Technology center, Grant No. NSF-STC88-09648.
Rights and permissions
About this article
Cite this article
Reingold, N., Westbrook, J. & Sleator, D.D. Randomized competitive algorithms for the list update problem. Algorithmica 11, 15–32 (1994). https://doi.org/10.1007/BF01294261
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01294261