Abstract (Joan Boyar)
We investigate the problem of giving seat reservations on-line. We
assume that a train travels from a start station to an end station,
stopping at a fixed number of stations. Passengers may attempt to
make reservations at any point before they get on the train.
The train has a fixed number of seats, and
the seat reservation system attempts to maximize income.
Since passengers must be assigned to seats when they buy their
seat reservations, rather than after the system knows about all
future requests for seat reservations, this is what is known as an
on-line problem. (An off-line algorithm would know about all requests
before making any seat assignments.)
The standard performance measure used for analyzing on-line algorithms is
the competitive ratio, which is the worst case ratio of what an on-line
algorithm does to what the optimal off-line algorithm does on the same
sequence of requests. In addition to considering the competitive ratio,
we also define the accommodating ratio which
is similar except that the only sequences of
requests allowed are sequences which could all have been accommodated by
the optimal off-line algorithm. We prove upper and lower bound
results for two different pricing policies.
This is joint work with Kim S. Larsen.
Last modified: August 7, 1997.
Kim Skak Larsen
(kslarsen@imada.sdu.dk)