Nested and Interleaved Ticketing for Multiple Travelers

Dongyu Lv; Yizhi Song; Chao Xu

doi:10.1007/978-981-97-7752-5_7

Nested and Interleaved Ticketing for Multiple Travelers

Dongyu Lv, Yizhi Song, Chao Xu^*

^*Corresponding author for this work

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

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	https://doi.org/10.1007/978-981-97-7752-5_7
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	https://ijtcs2024.comp.polyu.edu.hk/

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

Access Output

10.1007/978-981-97-7752-5_7

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Lv, D., Song, Y., & Xu, C. (2025). Nested and Interleaved Ticketing for Multiple Travelers. In B. Li, M. Li, & X. Sun (Eds.), Frontiers of Algorithmics: 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings (pp. 94-105). (Lecture Notes in Computer Science; Vol. 14752). Springer . https://doi.org/10.1007/978-981-97-7752-5_7

@inproceedings{cf6f4e435a9947d58f611a9948cad1e8,

title = "Nested and Interleaved Ticketing for Multiple Travelers",

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 {\textquoteleft}covert{\textquoteright} 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. {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.",

keywords = "Airline booking ploys, Dynamic programming, Matching",

author = "Dongyu Lv and Yizhi Song and Chao Xu",

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).; 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024) ; Conference date: 29-07-2024 Through 31-07-2024",

year = "2025",

doi = "10.1007/978-981-97-7752-5_7",

language = "English",

isbn = "978-981-97-7751-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer ",

pages = "94--105",

editor = "Bo Li and Minming Li and Xiaoming Sun",

booktitle = "Frontiers of Algorithmics",

url = "https://ijtcs2024.comp.polyu.edu.hk/",

}

Lv, D, Song, Y & Xu, C 2025, Nested and Interleaved Ticketing for Multiple Travelers. in B Li, M Li & X Sun (eds), Frontiers of Algorithmics: 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings. Lecture Notes in Computer Science, vol. 14752, Springer , pp. 94-105, 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024), Hong Kong, 29/07/24. https://doi.org/10.1007/978-981-97-7752-5_7

Nested and Interleaved Ticketing for Multiple Travelers. / Lv, Dongyu; Song, Yizhi; Xu, Chao.
Frontiers of Algorithmics: 18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings. ed. / Bo Li; Minming Li; Xiaoming Sun. Springer , 2025. p. 94-105 (Lecture Notes in Computer Science; Vol. 14752).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - Nested and Interleaved Ticketing for Multiple Travelers

AU - Lv, Dongyu

AU - Song, Yizhi

AU - Xu, Chao

N1 - 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).

PY - 2025

Y1 - 2025

N2 - 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.

AB - 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.

KW - Airline booking ploys

KW - Dynamic programming

KW - Matching

UR - http://www.scopus.com/inward/record.url?scp=85215313681&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85215313681&origin=recordpage

U2 - 10.1007/978-981-97-7752-5_7

DO - 10.1007/978-981-97-7752-5_7

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 978-981-97-7751-8

T3 - Lecture Notes in Computer Science

SP - 94

EP - 105

BT - Frontiers of Algorithmics

A2 - Li, Bo

A2 - Li, Minming

A2 - Sun, Xiaoming

PB - Springer

T2 - 5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024)

Y2 - 29 July 2024 through 31 July 2024

ER -

Nested and Interleaved Ticketing for Multiple Travelers

Abstract

Publication series

Conference

Bibliographical note

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this