On-line seat reservations via off-line seating arrangements

Jens S. Kohrt and Kim S. Larsen. On-line seat reservations via off-line seating arrangements. International Journal of Foundations of Computer Science, 16(2):381-397, April 2005.
When reservations are made to for instance a train, it is an on-line problem to accept or reject, i.e., decide if a person can be fitted in given all earlier reservations. However, determining a seating arrangement, implying that it is safe to accept, is an off-line problem with the earlier reservations and the current one as input. We develop algorithms with optimal running time to handle problems of this nature.
Available as ps (342 KB), ps.gz (156 KB), and pdf (153 KB).
Also available at WorldSciNet.
Related Papers:

See also other papers by Jens Svalgaard Kohrt.