The relative worst order ratio is a new measure for the quality of on-line algorithms, which has been giving new separations and even new algorithms for a variety of problems. Here, we apply the relative worst order ratio to the Seat Reservation Problem, the problem of assigning seats to passengers in a train. We consider the unit price problem, where all tickets have the same cost, and the proportional price problem, where the ticket price is proportional to the distance travelled.
Using the relative worst order ratio, we show that First-Fit and Best-Fit are better than Worst-Fit, for the unit price problem, even though they have not been separated using the competitive ratio. The same relative worst order ratio result holds for the proportional price problem, where no deterministic algorithm has a competitive ratio, or even a competitive ratio on accommodating sequences, which is bounded below by a constant.
Comparing algorithms to OPT with the relative worst order ratio gives the worst order ratio. The worst order ratio of any deterministic algorithm for either the unit price problem or the proportional price problem is always bounded above by the competitive ratio on accommodating sequences for the algorithm and bounded below by the competitive ratio on accommodating sequences for some algorithm. Thus, for the unit price problem, the worst order ratio of any algorithm is at least 1/2, even though the competitive ratio is not bounded below by any constant. This gives a much more optimistic and realistic view of how well the algorithms perform, but it is still necessary to use the relative worst order ratio to separate their performances.