Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Better Bounds on the Accommodating Ratio for the Seat Reservation Problem
Extended Abstract

Eric BachContact Information, Joan BoyarContact Information, Tao Jiang9, 10 Contact Information, Kim S. LarsenContact Information and Guo-Hui Lin9, 11 Contact Information

(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.

Contact Information Eric Bach
Email: bach@cs.wisc.edu

Contact Information Joan Boyar
Email: joan@imada.sdu.dk

Contact Information Tao Jiang
Email: jiang@cs.ucr.edu

Contact Information Kim S. Larsen
Email: kslarsen@imada.sdu.dk

Contact Information Guo-Hui Lin
Email: ghlin@math.uwaterloo.ca
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb22
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)