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. Technical Report PP-2003-08, Department of Mathematics and Computer Science, University of Southern Denmark, Odense, 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.

Availability:

Available as ps.gz (116 KB) and pdf (171 KB).
Also available at the DMF Preprint Server.

Related Papers:

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