Seat Reservation Allowing Seat Changes
Joan Boyar, Susan Krarup, Morten N. Nielsen · Electronic Notes in Theoretical Computer Science · 2001
We consider a new variant of the Seat Reservation Problem [4]in which seat changes are allowed. We analyze the problem using the competitive ratio and the competitive ratio on accommodating sequences [4]. A very promising algorithm defined 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, for which we prove very high performance guarantees. For instance when assuming that all of the passengers could have been seated by an optimal off-line algorithm, at least 2 3 of the passengers can be seated on-line with only one seat change and at least 3 4 will be seated if two seat changes are allowed. This should be compared to the performance guarantee of 1 2 for the best deterministic on-line algorithm when no seat changes are allowed [2].