ALCOMFT-TR-01-49 |
![]() |
Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, Guo-Hui Lin and Rob van Stee
Tight Bounds on the Competitive Ratio on Accommodating Sequences
Århus. Work packages 3 and 4. May 2001.Abstract: The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k stations. We are considering the version where all tickets have the same price and where requests are treated fairly, i.e., a request which can be fulfilled must be granted.Postscript file: ALCOMFT-TR-01-49.ps.gz (117 kb).For fair deterministic algorithms, we provide an asymptotically matching upper bound to the existing lower bound which states that all fair algorithms for this problem are (1)/(2)-competitive on accommodating sequences, when there are at least three seats.
Additionally, we give an asymptotic upper bound of (7)/(9) for fair randomized algorithms against oblivious adversaries.
We also examine concrete on-line algorithms, First-Fit and Random, for the special case of two seats. Tight analyses of their performance are given.