- Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.
- Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, and Guo-Hui Lin.
In 6th Annual International Computing and Combinatorics Conference (COCOON), volume 1858 of Lecture Notes in Computer Science, pages 221-231. Springer, 2000.
In a recent paper ([J. Boyar and K.S. Larsen, The seat reservation problem,
, 25 (1999), 403-417]), the seat reservation problem
It was shown that for the unit price problem
, where all tickets have the
same price, all "fair" algorithms are at least 1/2
while no fair algorithm is more than (4/5 +O(1/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
It is shown that better upper bounds exist for the special
cases with n=2
, and 4
A concrete on-line algorithm First-Fit is also examined for the special case
, for which we show that it is asymptotically optimal.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.