- 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.
- 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 by the author.