TY - JOUR
T1 - The relative worst order ratio applied to seat reservation
AU - Boyar, Joan
AU - Medvedev, Paul
PY - 2008/8/1
Y1 - 2008/8/1
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=50849119094&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=50849119094&partnerID=8YFLogxK
U2 - 10.1145/1383369.1383379
DO - 10.1145/1383369.1383379
M3 - Article
AN - SCOPUS:50849119094
SN - 1549-6325
VL - 4
JO - ACM Transactions on Algorithms
JF - ACM Transactions on Algorithms
IS - 4
M1 - 48
ER -