The relative worst order ratio applied to paging

ABSTRACT

The relative worst order ratio, a new measure for the quality of on-line algorithms, was recently defined and applied to two bin packing problems. Here, we apply it to the paging problem and obtain the following results: We devise a new deterministic paging algorithm, Retrospective-LRU, and show that it performs better than LRU. This is supported by experimental results, but contrasts with the competitive ratio. All deterministic marking algorithms have the same competitive ratio, but here we find that LRU is better than FWF. According to the relative worst order ratio, no deterministic marking algorithm can be significantly better than LRU, but the randomized algorithm MARK is better than LRU. Finally, look-ahead is shown to be a significant advantage, in contrast to the competitive ratio, which does not reflect that look-ahead can be helpful.

REFERENCES

• 1: Dimitris Achlioptas , Marek Chrobak , John Noga, Competitive analysis of randomized paging algorithms, Theoretical Computer Science, v.234 n.1-2, p.203-218, March 6, 2000 [doi>10.1016/S0304-3975(98)00116-9 ]
• 2: S. Albers. On the influence of lookahead in competitive paging algorithms. Algorithmica, 18:283--305, 1997.
• 3: Susanne Albers , Lene M. Favrholdt , Oliver Giel, On paging with locality of reference, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509949]
• 4: L. A. Belady. A study of replacement algorithms for virtual storage computers. IBM Systems Journal, 5:78--101, 1966.
• 5: S. Ben-David and A. Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11(1):73--91, 1994.
• 6: Allan Borodin , Sandy Irani , Prabhakar Raghavan , Baruch Schieber, Competitive paging with locality of reference, Journal of Computer and System Sciences, v.50 n.2, p.244-258, April 1995
• 7: J. Boyar and L. M. Favrholdt. The relative worst order ratio for on-line algorithms. In 5th Italian Conference on Algorithms and Complexity, volume 2653 of LNCS, pages 58--69, 2003.
• 8: J. Boyar and K. S. Larsen. The seat reservation problem. Algorithmica, 25:403--417, 1999.
• 9: Joan Boyar , Kim S. Larsen , Morten N. Nielsen, The Accommodating Function: A Generalization of the Competitive Ratio, SIAM Journal on Computing, v.31 n.1, p.233-258, 2001 [doi>10.1137/S0097539799361786]
• 10: J. Boyar and P. Medvedev. The relative worst order ratio applied to seat reservation. In Proceedings of the Ninth Scandinavian Workshop on Algorithm Theory, volume 3111 of LNCS, pages 90--101, 2004.
• 11: Dany Breslauer, On competitive on-line paging with lookahead, Theoretical Computer Science, v.209 n.1-2, p.365-375, Dec. 6, 1998 [doi>10.1016/S0304-3975(98)00118-2 ]
• 12: M. Chrobak and J. Noga. LRU Is Better than FIFO. Algorithmica, 23:180--185, 1999.
• 13: L. Epstein, L. M. Favrholdt, and J. S. Kohrt. The relative worst order ratio applied to scheduling problems. Manuscript, 2004.
• 14: Amos Fiat , Richard M. Karp , Michael Luby , Lyle A. McGeoch , Daniel D. Sleator , Neal E. Young, Competitive paging algorithms, Journal of Algorithms, v.12 n.4, p.685-699, Dec. 1991 [doi>10.1016/0196-6774(91)90041-V]
• 15: Amos Fiat , Ziv Rosen, Experimental studies of access graph based heuristics: beating the LRU standard?, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.63-72, January 05-07, 1997, New Orleans, Louisiana, United States
• 16: R. L. Graham. Bounds for certain multiprocessing anomalies. Bell Systems Technical Journal, 45:1563--1581, 1966.
• 17: D. S. Johnson. Fast algorithms for bin packing. Journal of Computer and System Sciences, 8:272--314, 1974.
• 18: Bala Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance, Journal of the ACM (JACM), v.47 n.4, p.617-643, July 2000 [doi>10.1145/347476.347479]
• 19: A. R. Karlin, M. S. Manasse, L. Rudolph, and D. D. Sleator. Competitive snoopy caching. Algorithmica, 3(1):79--119, 1988.
• 20: Anna R. Karlin , Steven J. Phillips , Prabhakar Raghavan, Markov Paging, SIAM Journal on Computing, v.30 n.3, p.906-922, 2000 [doi>10.1137/S0097539794268042]
• 21: Claire Kenyon, Best-fit bin-packing with random order, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.359-364, January 28-30, 1996, Atlanta, Georgia, United States
• 22: E. Koutsoupias and C. H. Papadimitriou. Beyond competitive analysis. In 35th Annual Symposium on Foundations of Computer Science, pages 394--400, 1994.
• 23: Sven Oliver Krumke , Willem de Paepe , Jörg Rambau , Leen Stougie, Online Bin Coloring, Proceedings of the 9th Annual European Symposium on Algorithms, p.74-85, August 28-31, 2001
• 24: L. A. McGeoch and D. D. Sleator. A strongly competitive randomized paging algorithm. Algorithmica, 6:816--825, 1991.
• 25: P. Raghavan. A statistical adversary for on-line algorithms. In D. D. Sleator L. A. McGeoch, editor, On-Line Algorithms, volume 7 of Series in Discrete Mathematics and Theoretical Computer Science, pages 79--83. American Mathematical Society, 1992.
• 26: Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
• 27: E. Torng. A unified analysis of paging and caching. Algorithmica, 20:175--200, 1998.
• 28: Neal Young, Competitive paging and dual-guided on-line weighted caching and watching algorithms, Princeton University, Princeton, NJ, 1992
• 29: N. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11:525--541, 1994.