The relative worst order ratio applied to seat reservation

ABSTRACT

The seat reservation problem is the problem of assigning passengers to seats on a train with n seats and k stations enroute in an online manner. The performance of algorithms for this problem is studied using the relative worst order ratio, a fairly new measure for the quality of online algorithms, which allows for direct comparisons between algorithms. This study has yielded new separations between algorithms. For example, for both variants of the problem considered, using the relative worst order ratio, First-Fit and Best-Fit are shown to be better than Worst-Fit.

REFERENCES

• 1: 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]
• 2: Ben-David, S., and Borodin, A. 1994. A new measure for the study of online algorithms. Algorithmica 11, 1, 73--91.
• 3: Joan Boyar , Lene M. Favrholdt, The relative worst order ratio for online algorithms, ACM Transactions on Algorithms (TALG), v.3 n.2, p.22-es, May 2007 [doi>10.1145/1240233.1240245]
• 4: Joan Boyar , Lene M. Favrholdt , Kim S. Larsen, The relative worst-order ratio applied to paging, Journal of Computer and System Sciences, v.73 n.5, p.818-843, August, 2007 [doi>10.1016/j.jcss.2007.03.001]
• 5: Boyar, J., Favrholdt, L. M., Larsen, K. S., and Nielsen, M. N. 2003. Extending the accommodating function. Acta Informatica 40, 3--35.
• 6: Boyar, J., and Larsen, K. S. 1999. The seat reservation problem. Algorithmica 25, 403--417.
• 7: 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]
• 8: Boyar, J., and Medvedev, P. 2007. The relative worst order ratio applied to seat reservation. Tech. rep. PP--2007--03, Department of Mathematics and Computer Science, University of Southern Denmark.
• 9: Chrobak, M., and Ślusarek, M. 1988. On some packing problems relating to dynamical storage allocation. RAIRO Theoret. Inform. Appl. 22, 487--499.
• 10: Dorrigiv, R., and López-Ortiz, A. 2005. A survey of performance measures for online algorithms. SIGACT News 36, 3, 1--17.
• 11: Epstein, L., Favrholdt, L. M., and Kohrt, J. S. 2006. Separating online scheduling algorithms with the relative worst order ratio. J. Combin. Optim. 12, 4, 362--385.
• 12: Graham, R. L. 1966. Bounds for certain multiprocessing anomalies. Bell Systems Tech. J. 45, 1563--1581.
• 13: Ronald L. Graham , Donald E. Knuth , Oren Patashnik, Concrete Math, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 14: Johnson, D. S. 1974. Fast algorithms for bin packing. J. Comput. Syst. Sci. 8, 272--314.
• 15: Karlin, A. R., Manasse, M. S., Rudolph, L., and Sleator, D. D. 1988. Competitive snoopy caching. Algorithmica 3, 1, 79--119.
• 16: 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
• 17: Kierstead, H. A., and Trotter, W. T. 1981. An extremal problem in recursive combinatorics. Congressus Numerantium 33, 143--153.
• 18: Kohrt, J. S. 2004. Online algorithms under new assumptions. Ph.D. thesis, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark.
• 19: 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]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms

Keywords:
Online, quality measure, relative worst order ratio, seat reservation