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

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

Conference

ConferenceEighth International Workshop on Algorithms and Data Structures
Country/TerritoryCanada
CityOttawa
Period30/07/200301/08/2003
SeriesLecture Notes in Computer Science
Volume2748

Cite this