Improving the Competitive Ratios of the Seat Reservation Problem

Abstract : In the seat reservation problem, there are k stations, s1 through sk, and one train with n seats departing from the station s1 and arriving at the station sk. Each passenger orders a ticket from station si to station sj (1 ≤ i < j ≤ k) by specifying i and j. The task of an online algorithm is to assign one of n seats to each passenger online, i.e., without knowing future requests. The purpose of the problem is to maximize the total price of the sold tickets. There are two models, the unit price problem and the proportional price problem, depending on the pricing policy of tickets. In this paper, we improve upper and lower bounds on the competitive ratios for both models: For the unit price problem, we give an upper bound of $\frac{4}{k-2\sqrt{k-1}+4}$, which improves the previous bound of $\frac{8}{k+5}$. We also give an upper bound of $\frac{2}{k-2\sqrt{k-1}+2}$ for the competitive ratio of Worst-Fit algorithm, which improves the previous bound of $\frac{4}{k-1}$. For the proportional price problem, we give upper and lower bounds of $\frac{3+\sqrt{13}}{k-1+\sqrt{13}} (\simeq \frac{6.6}{k+2.6})$ and $\frac{2}{k-1}$, respectively, on the competitive ratio, which improves the previous bounds of $\frac{4+2\sqrt{13}}{k+3+2\sqrt{13}} (\simeq \frac{11.2}{k+10.2})$ and $\frac{1}{k-1}$, respectively.
Type de document :
Communication dans un congrès
Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.328-339, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_24〉
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01054449
Contributeur : Hal Ifip <>
Soumis le : mercredi 6 août 2014 - 16:24:52
Dernière modification le : mercredi 9 août 2017 - 12:03:26
Document(s) archivé(s) le : mercredi 26 novembre 2014 - 00:57:00

Fichier

03230328.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Shuichi Miyazaki, Kazuya Okamoto. Improving the Competitive Ratios of the Seat Reservation Problem. Cristian S. Calude; Vladimiro Sassone. 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS) / Held as Part of World Computer Congress (WCC), Sep 2010, Brisbane, Australia. Springer, IFIP Advances in Information and Communication Technology, AICT-323, pp.328-339, 2010, Theoretical Computer Science. 〈10.1007/978-3-642-15240-5_24〉. 〈hal-01054449〉

Partager

Métriques

Consultations de la notice

112

Téléchargements de fichiers

119