**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)