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 WorksRGC 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 languageEnglish
    Title of host publicationFrontiers of Algorithmics
    Subtitle of host publication18th International Joint Conference, IJTCS-FAW 2024, Hong Kong SAR, China, July 29-31, 2024, Proceedings
    EditorsBo Li, Minming Li, Xiaoming Sun
    PublisherSpringer 
    Pages94-105
    ISBN (Electronic)978-981-97-7752-5
    ISBN (Print)978-981-97-7751-8
    DOIs
    Publication statusPublished - 2025
    Event5th 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 202431 Jul 2024
    https://ijtcs2024.comp.polyu.edu.hk/

    Publication series

    NameLecture Notes in Computer Science
    Volume14752
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference5th International Joint Conference on Theoretical Computer Science (IJTCS) and 18th International Conference on Frontiers of Algorithmic Wisdom (FAW) (IJTCS-FAW 2024)
    Country/TerritoryHong Kong
    Period29/07/2431/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

    Fingerprint

    Dive into the research topics of 'Nested and Interleaved Ticketing for Multiple Travelers'. Together they form a unique fingerprint.

    Cite this