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.