TY - CHAP
T1 - The relative worst order ratio applied to seat reservation
AU - Boyar, Joan
AU - Medvedev, Paul
PY - 2004
Y1 - 2004
N2 - The relative worst order ratio is a new measure for the quality of online 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. For the unit price problem, where all tickets have the same cost, we show that First-Fit and Best-Fit are better than Worst-Fit, 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 the ticket price is proportional to the distance travelled. In contrast, no deterministic algorithm has a competitive ratio, or even a competitive ratio on accommodating sequences, which is bounded below by a constant. It is also shown that the worst order ratio for seat reservation algorithms is very closely related to the competitive ratio on accommodating sequences.
AB - The relative worst order ratio is a new measure for the quality of online 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. For the unit price problem, where all tickets have the same cost, we show that First-Fit and Best-Fit are better than Worst-Fit, 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 the ticket price is proportional to the distance travelled. In contrast, no deterministic algorithm has a competitive ratio, or even a competitive ratio on accommodating sequences, which is bounded below by a constant. It is also shown that the worst order ratio for seat reservation algorithms is very closely related to the competitive ratio on accommodating sequences.
UR - http://www.scopus.com/inward/record.url?scp=21144455932&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=21144455932&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-27810-8_9
DO - 10.1007/978-3-540-27810-8_9
M3 - Chapter
AN - SCOPUS:21144455932
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 90
EP - 101
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Hagerup, Torben
A2 - Katajainen, Jyrki
PB - Springer Verlag
ER -