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: Eric Bach , Joan Boyar , Leah Epstein , Lene M. Favrholdt , Tao Jiang , Kim S. Larsen , Guo-Hui Lin , Rob Van Stee, Tight bounds on the competitive ratio on accommodating sequences for the seat reservation problem, Journal of Scheduling, v.6 n.2, p.131-147, March/April 2003 [doi>10.1023/A:1022985808959]
• 3: Eric Bach , Joan Boyar , Tao Jiang , Kim S. Larsen , Guo-Hui Lin, Better Bounds on the Accommodating Ratio for the Seat Reservation Problem, Proceedings of the 6th Annual International Conference on Computing and Combinatorics, p.221-231, July 26-28, 2000
• 4: Avrim Blum , John Dunagan, Smoothed analysis of the perceptron algorithm for linear programming, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.905-914, January 06-08, 2002, San Francisco, California
• 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: Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst order ratio applied to paging, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 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: 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
• 10: Joan Boyar , Susan Krarup , Morten N. Nielsen, Seat reservation allowing seat changes, Journal of Algorithms, v.52 n.2, p.169-192, August 2004 [doi>10.1016/j.jalgor.2004.02.002]
• 11: {BL99} Joan Boyar and Kim S. Larsen. The Seat Reservation Problem. Algorithmica, 25(4):403--417, 1999.
• 12: Luca Becchetti , Stefano Leonardi , Alberto Marchetti-Spaccamela , Guido Schäfer , Tjark Vredeveld, Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.462, October 11-14, 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: Joan Boyar , Kim S. Larsen , Morten N. Nielsen, Separating the Accommodating Ratio from the Competitive Ratio, University of Southern Denmark, 1999
• 15: 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]
• 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: Joan Boyar , Morten N. Nielsen, An Improved Lower Bound on First-Fit''s Accommodating Ratio for the Unit Price Bin Packing Problem, University of Southern Denmark, 1999
• 19: L. A. Belady , R. A. Nelson , G. S. Shedler, An anomaly in space-time characteristics of certain programs running in a paging machine, Communications of the ACM, v.12 n.6, p.349-353, June 1969 [doi>10.1145/363011.363155]
• 20: {CN99} Marek Chrobak and John Noga. LRU is better than FIFO. Algorithmica, 23(2):180--185, 1999.
• 21: Leah Epstein , Lene M. Favrholdt, On-line maximizing the number of items packed in variable-sized bins, Acta Cybernetica, v.16 n.1, p.57-66, January 2003
• 22: 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
• 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: Amos Fiat , Gerhard J. Woeginger, Competitive Odds and Ends, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.385-394, January 1998
• 25: {Gal79} Shmuel Gal. Search games with mobile and immobile hider. SIAM Journal of Control and Optimization, 17:99--122, 1979.
• 26: Sandy Irani , Anna R. Karlin , Steven Phillips, Strongly Competitive Algorithms for Paging with Locality of Reference, SIAM Journal on Computing, v.25 n.3, p.477-497, June 1996 [doi>10.1137/S0097539792236353]
• 27: Sandy Irani, Competitive Analysis of Paging, Developments from a June 1996 seminar on Online algorithms: the state of the art, p.52-73, January 1998
• 28: 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
• 29: B. Kalyanasundaram , Kirk Pruhs, Speed is as powerful as clairvoyance [scheduling problems], Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.214, October 23-25, 1995
• 30: Elias Koutsoupias , Christos H. Papadimitriou, Beyond Competitive Analysis, SIAM Journal on Computing, v.30 n.1, p.300-317, 2000 [doi>10.1137/S0097539796299540]
• 31: Elias Koutsoupias , Christos H. Papadimitriou , Mihalis Yannakakis, Searching a Fixed Graph, Proceedings of the 23rd International Colloquium on Automata, Languages and Programming, p.280-289, July 08-12, 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: 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]
• 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: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]
• 37: {You94} Neal E. Young. The k-server dual and loose competitiveness for paging. Algorithmica, 11(6):525--541, June 1994.
• 38: Neal E. Young, Bounding the diffuse adversary, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.420-425, January 25-27, 1998, San Francisco, California, United States
• 39: Neal E. Young, On-line paging against adversarially biased random inputs, Journal of Algorithms, v.37 n.1, p.218-235, Oct. 2000 [doi>10.1006/jagm.2000.1099]
• 40: {You02} N. E. Young. On-line file caching. Algorithmica, 33(3):371--383, 2002.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.m MISCELLANEOUS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Numerical algorithms

General Terms:
Documentation