TY - GEN

T1 - Better Bounds on the Accommodating Ratio for the Seat Reservation Problem

AU - Bach, Eric

AU - Boyar, Joan

AU - Jiang, Tao

AU - Larsen, Kim Skak

AU - Lin, Guo-Hui

PY - 2000

Y1 - 2000

N2 - In a recent paper [J. Boyar and K. S. Larsen, “The seat reservation problem”, Algorithmica 25, 403-417 (1999; Zbl 0937.68156)], 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.

AB - In a recent paper [J. Boyar and K. S. Larsen, “The seat reservation problem”, Algorithmica 25, 403-417 (1999; Zbl 0937.68156)], 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.

U2 - 10.1007/3-540-44968-x_22

DO - 10.1007/3-540-44968-x_22

M3 - Article in proceedings

T3 - Lecture Notes in Computer Science

SP - 221

EP - 231

BT - Computing and Combinatorics, 6th Annual International Conference, COCOON 2000

T2 - Sixth Annual International Computing and Combinatorics Conference

Y2 - 26 July 2000 through 28 July 2000

ER -