The Relative Worst Order Ratio Applied to Seat Reservation
Joan Boyar, Paul Medvedev
ACM Transactions on Algorithms

The seat reservation problem is the problem of assigning passengers to seats on a train with n seats and k stations en-route, in an on-line manner. The performance of algorithms for this problem is studied using the relative worst order ratio, a relatively new measure for the quality of on-line algorithms, which allows for direct comparisons between algorithms.

This study has yielded new separations between algorithms. For example, for the both variants problem of the problem considered, using the relative worst order ratio, First-Fit and Best-Fit are shown to be better than Worst-Fit.


Last modified: Thu May 15 11:26:28 CEST 2008
Joan Boyar (joan@imada.sdu.dk)