On-line seat reservations via off-line seating arrangements

Description:

Jens S. Frederiksen and Kim S. Larsen. On-line seat reservations via off-line seating arrangements. In Proceedings of the Eighth Workshop on Algorithms and Data Structures (WADS 2003), volume 2748 of Lecture Notes in Computer Science, pages 174-185. Springer-Verlag, 2003.

Abstract:

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 optimal algorithms to handle problems of this nature.

Copyright:

This paper is © Springer-Verlag.

Availability:

Available as ps (262 KB), ps.gz (121 KB), and pdf (157 KB).
Also available at SpringerLink.
The slides of my talk are available as ps (237 KB), ps.gz (64 KB), and pdf (1106 KB).

Related Papers:

• On-line seat reservations via off-line seating arrangements (Journal Paper)
• On-line seat reservations via off-line seating arrangements (Technical Report)