On-Line Seat Reservations via Off-Line Seating Arrangements.

Jens S. Frederiksen and Kim S. Larsen.
In 8th International Workshop on Algorithms and Data Structures (WADS), volume 2748 of Lecture Notes in Computer Science, pages 174-185. Springer, 2003.

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.

---

publication

Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any): The final publication is available at link.springer.com.

full version

Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.

other publications

Other publications by the author.