SIGACT news online algorithms column 8

Abstract

Pros and cons of the competitive analysis have been discussed in the literature by many authors. Continuing this discussion in this quarter s column, Reza Dorrigiv and Alejandro Lopez-Ortiz review and compare various performance measures for online algorithms, highlighting their differences with respect to the competitive ratio. Many thanks to Reza and Alejandro for contributing this article.

References

1. {ABE+02} Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen. Fair versus Unrestricted Bin Packing. Algorithmica, 34(2):181--196, 2002.]]
2. {BBE+03} Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, Guo hui Lin, and Rob Van Stee. Tight bounds on the competitive ratio on accommodating sequenced for the seat reservation problem. Journal of Scheduling, 6(2):131--147, 2003.]]
3. {BBJ+00} Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, and Guo-Hui Lin. Better Bounds on the Accommodating Ratio for the Seat Reservation Problem. In Sixth Annual International Computing and Combinatorics Conference, volume 1858 of Lecture Notes in Computer Science, pages 221--231. Springer-Verlag, 2000.]]
4. {BD02} Avrim Blum and John Dunagan. Smoothed analysis of the perceptron algorithm for linear programming. In Proceedings of the 13th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA-02), pages 905--914, 2002.]]
5. {BDB94} Shai Ben-David and Allan Borodin. A new measure for the study of on-line algorithms. Algorithmica, 11:73--91, 1994.]]
6. {BF03} Joan Boyar and Lene M. Favrholdt. The relative worst order ratio for on-line algorithms. In CIAC: Italian Conference on Algorithms and Complexity, 2003.]]
7. {BFL05} Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen. The Relative Worst Order Ratio Applied to Paging. In Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 718--727. ACM Press, 2005.]]
8. {BFLN03} Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen. Extending the Accommodating Function. Acta Informatica, 40(1):3--35, 2003.]]
9. {BIRS95} Allan Borodin, Sandy Irani, Prabhakar Raghavan, and Baruch Schieber. Competitive paging with locality of reference. Journal of Computer and System Sciences, 50:244--258. 1995.]]
10. {BKN04} Joan Boyar, Susan Krarup, and Morten N. Nielsen. Seat reservation allowing seat changes. Journal of Algorithms, 52(2):169--192, 2004.]]
11. {BL99} Joan Boyar and Kim S. Larsen. The Seat Reservation Problem. Algorithmica, 25(4):403--417, 1999.]]
12. {BLMS+03} L. Becchetti, S. Leonardi, A. Marchetti-Spaccamela, G. Schafer, and T. Vredeveld. Average case and smoothed competitive analysis of the multi-level feedback algorithm. In IEEE, editor, Proceedings: 44th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2003, 11--14 October 2003, Cambridge, Massachusetts, pages 462--471, 2003.]]
13. {BLN98} Joan Boyar, Kim S. Larsen, and Morten N. Nielsen. The accommodating function - a generalization of the competitive ratio. Technical Report PP-1998-24; Department of Mathematics and Computer Science, Odense University, December 22 1998. Mon, 6 Nov 2000 09:44:21 GMT.]]
14. {BLN99} Joan Boyar, Kim S. Larsen, and Morten N. Nielsen. Separating the accommodating ratio from the competitive ratio. Technical Report PP-1999-03, Department of Mathematics and Computer Science, Odense University, January 25 1999.]]
15. {BLN01} Joan Boyar, Kim S. Larsen, and Morten N. Nielsen. The Accommodating Function: A generalization of the competitive ratio. SIAM Journal on Computing, 31(1):233--258, 2001.]]
16. {BM04} Joan Boyar and Paul Medvedev. The relative worst order ratio applied to seat reservation. In SWAT: Scandinavian Workshop on Algorithm Theory, 2004.]]
17. {BMB03} Cyril Banderier, Kurt Mehlhorn, and Rene Beier. Smoothed analysis of three combinatorial problems. In MFCS: Symposium on Mathematical Foundations of Computer Science, volume 2747, pages 198--207, 2003.]]
18. {BN99} Joan Boyar and Morten N. Nielsen. An improved lower bound on first-fit s accommodating ratio for the unit price bin packing problem. Technical Report PP-1999-11, Department of Mathematics and Computer Science, Odense University, June 10 1999.]]
19. {BNS69} L. A. Belady, R. A. Nelson, and G. S. Shedler. An anomaly in space-time characteristics of certain programs running in a paging machine. Communications of the ACM, 12(6):349--353, June 1969.]]
20. {CN99} Marek Chrobak and John Noga. LRU is better than FIFO. Algorithmica, 23(2):180--185, 1999.]]
21. {EF03} Leah Epstein and Lene M. Favrholdt. On-line maximizing the number of items packed in variable-sized bins. Acta Cybernetica, 16(1):57--66, 2003.]]
22. {FR97} Amos Fiat and Ziv Rosen. Experimental studies of access graph based heuristics: Beating the LRU standard? In Proc. 8th Symp. on Discrete Algorithms (SODA), pages 63--72. ACM/SIAM, 1997.]]
23. {FSBY+04} Ariel Felner, Roni Stern, Asaph Ben-Yair, Sarit Kraus, and Nathan Netanyahu. PHA*: Finding the shortest path with A* in an unknown physical environment. Journal of Artificial Intelligence Research, 21:631--670, 2004.]]
24. {FW98} Amos Fiat and Gerhard J. Woeginger. Competitive odds and ends. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms --- The State of the Art, volume 1442 of LNCS, pages 385--394. Springer-Verlag, 1998.]]
25. {Gal79} Shmuel Gal. Search games with mobile and immobile hider. SIAM Journal of Control and Optimization, 17:99--122, 1979.]]
26. {IKP96} Sandy Irani, Anna R. Karlin, and Steven Phillips. Strongly competitive algorithms for paging with locality of reference. SIAM J. Comput., 25:477--497, 1996.]]
27. {Ira98} Sandy Irani. Competitive analysis of paging. In Amos Fiat and Gerhard J. Woeginger, editors, Online Algorithms --- The State of the Art, volume 1442 of LNCS, pages 52--73. Springer-Verlag, 1998.]]
28. {Ken96} Claire Kenyon. Best-fit bin-packing with random order. In Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 359--364, 1996.]]
29. {KP95} Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoyance. In 36th Annual Symposium on Foundations of Computer Science, pages 214--221, 23--25 October 1995.]]
30. {KP00} Elias Koutsoupias and Christos Papadimitriou. Beyond competitive analysis. SIAM J. Comput., 30:300--317, 2000.]]
31. {KPY96} Elias Koutsoupias, Christos Papadimitriou, and Mihalis Yannakakis. Searching a fixed graph. In International Colloquium on Automata, Languages, and Programming, volume 1099, pages 280--289, 1996.]]
32. {LO96} Alejandro Lopez-Ortiz. On-line target searching in bounded and unbounded domains. PhD thesis, University of Waterloo, 1996.]]
33. {MR05} Bodo Manthey and Rudiger Reischuk. Smoothed analysis of the height of binary search trees. Schriftenreihe der Institute fur Informatik und Mathematik A-05-17, Universitat zu Lubeck, Lubeck, June 2005.]]
34. {ST85} Daniel D. Sleator and Robert E. Tarjan. Amortized Efficiency of List Update and Paging Rules. Communications of the ACM, 28:202--208, 1985.]]
35. {ST03} Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of termination of linear programming algorithms. Mathematical Programming, 97(1--2):375--404, 2003.]]
36. {ST04} Daniel A. Spielman and Shang-Hua Teng. Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time. Journal of the ACM, 51(3):385--463, 2004.]]
37. {You94} Neal E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525--541, June 1994.]]
38. {You98} Neal E. Young. Bounding the diffuse adversary. In SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pages 420--425, 1998.]]
39. {You00} Neal E. Young. On-line paging against adversarially biased random inputs. J. Algorithms, 37(1):218--235, 2000.]]
40. {You02} N. E. Young. On-line file caching. Algorithmica, 33(3):371--383, 2002.]]

Index Terms

• General and reference

• Mathematics of computing

  • Mathematical analysis

    • Numerical analysis

      • Numerical differentiation

• Theory of computation

  • Design and analysis of algorithms