ALCOMFT-TR-03-31

Jens S. Frederiksen and Kim S. Larsen
On-Line Seat Reservations via Off-Line Seating Arrangements
Århus. Work package 3. September 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.

Postscript file: ALCOMFT-TR-03-31.ps.gz (135 kb).