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