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

Jens S. Kohrt and Kim S. Larsen.
International Journal of Foundations of Computer Science, 16(2): 381-397, 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.

---

publication

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

open access (184 KB)

The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.

other publications

Other publications by the author.