 The Seat Reservation Problem.
 Joan Boyar and Kim S. Larsen.
Algorithmica, 25(4): 403417, 1999.
We investigate the problem of giving seat reservations online. We
assume that a train travels from a start station to an end station,
stopping at
k stations, including the first and last.
Reservations can be made for any trip
going from any station to any later station.
The train has a fixed number of seats.
The seat reservation system attempts to maximize income. We consider the
case in which all tickets have the same price and the case in which the
price of a ticket is proportional to the length of the trip.
For both cases, we prove upper and lower bounds of
Theta(1/k) on the competitive
ratio of any "fair"
deterministic algorithm.
We also define the
accommodating ratio which
is similar to the competitive ratio except that the only sequences of
requests allowed are sequences for which the optimal offline algorithm
could accommodate all requests. We prove upper and lower bounds of
Theta(1) on
the accommodating ratio of any "fair" deterministic algorithm, in the
case in which all tickets have the same price,
but
Theta(1/k) in the case
in which the ticket price is proportional to the length of the trip.
The most surprising of these results is that all "fair" algorithms are at
least
1/2accommodating when all tickets have the same price.
We prove similar results bounding the performance of any "fair" randomized
algorithm against an adaptive online adversary.
We also consider concrete algorithms; more specifically,
FirstFit and BestFit.

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

open access (175 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.