ALCOMFT-TR-02-3

Joan Boyar, Susan Krarup and Morten N. Nielsen
Seat Reservation Allowing Seat Changes
Århus. Work packages 3 and 4. March 2002.

Abstract: We consider a variant of the Seat Reservation Problem in which seat changes are allowed. We analyze the model using the competitive ratio, the competitive ratio on accommodating sequences, and the accommodating function. A very promising family of algorithms considered in this paper is Min-Change, which will ask passengers to change seat, only if they would otherwise have been rejected. Min-Change belongs to a large class of conservative algorithms, which all have very high performance guarantees. For instance, if the optimal off-line algorithm can seat all of the passengers, \frac 23 of the passengers can be seated on-line using any conservative algorithm allowing only one seat change and \frac 34 will be seated if two seat changes are allowed. This should be compared to the asymptotically hardness result of \frac 12 for the best algorithm when no seat changes are allowed. Another interesting algorithm, Modified-Kierstead-Trotter, is proposed and shown to seat all passengers if the optimal off-line algorithm could have accommodated them with only half as many seats. On this type of sequences, Modified-Kierstead-Trotter is strictly better than Min-Change-First-Fit which is strictly better than the Checkerboard Algorithm.

Postscript file: ALCOMFT-TR-02-3.ps.gz (204 kb).