Better Bounds on the Accommodating Ratio for the Seat Reservation Problem
Extended Abstract
Eric Bach7
, Joan Boyar8
, Tao Jiang9, 10
, Kim S. Larsen8
and Guo-Hui Lin9, 11 
| (7) |
Computer Sciences Department, University of Wisconsin - Madison, 1210 West Dayton Street, Madison, WI, 53706-1685 |
| (8) |
Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark |
| (9) |
Department of Computer Science, University of California, Riverside, 92521 |
| (10) |
Department of Computing and Software, McMaster University, Hamilton, Ontario, L8S 4L7, Canada |
| (11) |
Department of Computer Science, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada |
Abstract
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 deterministic algorithm First-Fit and an on-line randomized algorithm Random are
also examined for the special case n = 2, where they are shown to be asymptotically optimal.
Keywords The seat reservation problem - on-line algorithms - accommodating ratio - adversary argument
Supported in part by NSF Grant CCR-9510244.
Part of this work was carried out while the author was visiting the Department of Computer Sciences, University of Wisconsin
- Madison. Supported in part by SNF (Denmark), in part by NSF (U.S.) grant CCR-9510244, and in part by the esprit Long Term
Research Programme of the EU under project number 20244 (alcom-it).
Supported in part by NSERC Research Grant OGP0046613, a CITO grant, and a UCR startup grant.
Supported in part by NSERC Research Grant OGP0046613 and a CITO grant.
References secured to subscribers.