Better Bounds on the Accommodating Ratio for the Seat Reservation Problem
Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, Guo-Hui Lin
Proceedings of the Sixth Annual International Computing and Combinatorics Conference, Lecture Notes in Computer Science 1858: 221-231, Springer-Verlag, 2000.

In a recent paper ([J. Boyar and K.S. Larsen, The seat reservation problem, Algorithmica, 25 (1999), 403-417]), the seat reservation problem was investigated. It was shown that for the unit price problem, where all tickets have the same price, all "fair" algorithms are at least 1/2-accommodating, while no fair algorithm is more than (4/5 +O(1/k))-accommodating, where k is the number of stations the train travels. In this paper, we design a more dextrous adversary argument, such that we improve the upper bound on the accommodating ratio to (7/9 +O(1/k)), even for fair randomized algorithms against oblivious adversaries. For deterministic algorithms, the upper bound is lowered to approximately .7699. It is shown that better upper bounds exist for the special cases with n=2, 3, and 4 seats. A concrete on-line algorithm First-Fit is also examined for the special case n=2, for which we show that it is asymptotically optimal.


Last modified: April 3, 2000.
Kim Skak Larsen (kslarsen@imada.sdu.dk)