Abstract
Nested ticketing represents a prevalent practice in airline bookings, employed to bypass certain airline ticketing regulations with the aim of reducing costs on multiple round-trip tickets. We consider the computational complexity of nested ticketing, and it is ‘covert’ version, which we call interleaved ticketing. Consider multiple agents living in different locations and a single client who demands that one agent be present each week. The objective for the company is to schedule these agents and arrange their flight itineraries to minimize the cost. We show that when nested ticketing is allowed, the problem is NP-hard when there are at least two agents. We also show there exists a polynomial-time algorithm if only interleaved ticketing is allowed, and the number of airlines is bounded. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
Original language | English |
---|---|
Title of host publication | Frontiers of Algorithmics |
Subtitle of host publication | 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings |
Editors | Bo Li, Minming Li, Xiaoming Sun |
Publisher | Springer |
Pages | 94-105 |
ISBN (Electronic) | 978-981-97-7752-5 |
ISBN (Print) | 978-981-97-7751-8 |
DOIs | |
Publication status | Published - 2025 |
Event | 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024) - Hong Kong Polytechnic University, Hong Kong Duration: 29 Jul 2024 → 31 Jul 2024 https://ijtcs2024.comp.polyu.edu.hk/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Volume | 14752 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024) |
---|---|
Country/Territory | Hong Kong |
Period | 29/07/24 → 31/07/24 |
Internet address |
Bibliographical note
Full text of this publication does not contain sufficient affiliation information. With consent from the author(s) concerned, the Research Unit(s) information for this record is based on the existing academic department affiliation of the author(s).Research Keywords
- Airline booking ploys
- Dynamic programming
- Matching