Seat Reservation Allowing Seat Changes
Joan Boyar, Susan Krarup, Morten N. Nielsen
Journal of Algorithms

We consider a variant of the Seat Reservation Problem [Boyar,Larsen 99] in which seat changes are allowed. We analyze the model using the competitive ratio, the competitive ratio on accommodating sequences [Boyar,Larsen 99], and the accommodating function [Boyar,Favrholdt,Larsen,Nielsen 03; Boyar,Larsen,Nielsen 01]. A very promising family of algorithms considered in this paper is Min-Change, which will ask passengers to change seats, 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, 2/3 of the passengers can be seated on-line using any conservative algorithm allowing only one seat change and 3/4 will be seated if two seat changes are allowed. This should be compared to the asymptotic hardness result of 1/2 for the best algorithm when no seat changes are allowed [Bach,Boyar,Epstein,Favrholdt,Jiang,Larsen,Lin,vanStee 03]. 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 sequence, Modified-Kierstead-Trotter is strictly better than Min-Change-First-Fit, which is strictly better than the Checkerboard Algorithm.


Last modified: May 5, 2003.
Joan Boyar (joan@imada.sdu.dk)