On-Line Seat Reservations via Off-Line Seating Arrangements

Jens S. Frederiksen, Kim Skak Larsen

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


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.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures, 8th International Workshop, WADS 2003
Number of pages12
Publication date2003
Publication statusPublished - 2003
EventEighth International Workshop on Algorithms and Data Structures - Ottawa, Canada
Duration: 30. Jul 20031. Aug 2003


ConferenceEighth International Workshop on Algorithms and Data Structures
SeriesLecture Notes in Computer Science

Cite this