Disjoint Tours and the Price of Diversity

Mark de Berg; Andrés López Martínez; Frits Spieksma

doi:10.1007/978-981-95-7127-7_27

Disjoint Tours and the Price of Diversity

Mark de Berg
, Andrés López Martínez (Corresponding author)
, Frits Spieksma

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as possible. We investigate the Price of Diversity (PoD) for this problem, which is the ratio of the cost of the longer of the two tours and the cost of a single optimal tour, in the worst case over all possible instances. We prove (almost) tight bounds on this quantity for a special 1-dimensional scenario and for general metric spaces. We believe that the Price-of-Diversity framework that we introduce is interesting in its own right, and may lead to follow-up work on other problems as well.

Original language	English
Title of host publication	WALCOM: Algorithms and Computation
Subtitle of host publication	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings
Editors	Emilio Di Giacomo, Debajyoti Mondal
Place of Publication	Singapore
Publisher	Springer
Pages	402-417
Number of pages	16
ISBN (Electronic)	978-981-95-7127-7
ISBN (Print)	978-981-95-7126-0
DOIs	https://doi.org/10.1007/978-981-95-7127-7_27
Publication status	Published - 14 Feb 2026
Event	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026 - Perugia, Italy Duration: 4 Mar 2026 → 6 Mar 2026

Publication series

Name	Lecture Notes in Computer Science (LNCS)
Volume	16444
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026
Country/Territory	Italy
City	Perugia
Period	4/03/26 → 6/03/26

Bibliographical note

Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

Keywords

Diverse Solutions
Path TSP
Price of Diversity
TSP

Access to Document

10.1007/978-981-95-7127-7_27

Cite this

de Berg, M., López Martínez, A., & Spieksma, F. (2026). Disjoint Tours and the Price of Diversity. In E. Di Giacomo, & D. Mondal (Eds.), WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings (pp. 402-417). (Lecture Notes in Computer Science (LNCS); Vol. 16444). Springer. https://doi.org/10.1007/978-981-95-7127-7_27

de Berg, Mark ; López Martínez, Andrés ; Spieksma, Frits. / Disjoint Tours and the Price of Diversity. WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings. editor / Emilio Di Giacomo ; Debajyoti Mondal. Singapore : Springer, 2026. pp. 402-417 (Lecture Notes in Computer Science (LNCS)).

@inproceedings{592ff4bcc7e0479290e11ad94cc63ce2,

title = "Disjoint Tours and the Price of Diversity",

abstract = "We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as possible. We investigate the Price of Diversity (PoD) for this problem, which is the ratio of the cost of the longer of the two tours and the cost of a single optimal tour, in the worst case over all possible instances. We prove (almost) tight bounds on this quantity for a special 1-dimensional scenario and for general metric spaces. We believe that the Price-of-Diversity framework that we introduce is interesting in its own right, and may lead to follow-up work on other problems as well.",

keywords = "Diverse Solutions, Path TSP, Price of Diversity, TSP",

author = "\{de Berg\}, Mark and \{L{\'o}pez Mart{\'i}nez\}, Andr{\'e}s and Frits Spieksma",

note = "Publisher Copyright: {\textcopyright} The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.; 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026 ; Conference date: 04-03-2026 Through 06-03-2026",

year = "2026",

month = feb,

day = "14",

doi = "10.1007/978-981-95-7127-7\_27",

language = "English",

isbn = "978-981-95-7126-0",

series = "Lecture Notes in Computer Science (LNCS)",

publisher = "Springer",

pages = "402--417",

editor = "\{Di Giacomo\}, Emilio and Debajyoti Mondal",

booktitle = "WALCOM: Algorithms and Computation",

address = "Germany",

}

de Berg, M , López Martínez, A & Spieksma, F 2026, Disjoint Tours and the Price of Diversity. in E Di Giacomo & D Mondal (eds), WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings. Lecture Notes in Computer Science (LNCS), vol. 16444, Springer, Singapore, pp. 402-417, 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, 4/03/26. https://doi.org/10.1007/978-981-95-7127-7_27

Disjoint Tours and the Price of Diversity. / de Berg, Mark ; López Martínez, Andrés (Corresponding author); Spieksma, Frits.
WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings. ed. / Emilio Di Giacomo; Debajyoti Mondal. Singapore: Springer, 2026. p. 402-417 (Lecture Notes in Computer Science (LNCS); Vol. 16444).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Disjoint Tours and the Price of Diversity

AU - de Berg, Mark

AU - López Martínez, Andrés

AU - Spieksma, Frits

N1 - Publisher Copyright: © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2026.

PY - 2026/2/14

Y1 - 2026/2/14

N2 - We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as possible. We investigate the Price of Diversity (PoD) for this problem, which is the ratio of the cost of the longer of the two tours and the cost of a single optimal tour, in the worst case over all possible instances. We prove (almost) tight bounds on this quantity for a special 1-dimensional scenario and for general metric spaces. We believe that the Price-of-Diversity framework that we introduce is interesting in its own right, and may lead to follow-up work on other problems as well.

AB - We study a variant of the Traveling Salesman Problem, where instead of finding a single tour, we want to find a pair of two edge-disjoint tours whose longer tour is as short as possible. We investigate the Price of Diversity (PoD) for this problem, which is the ratio of the cost of the longer of the two tours and the cost of a single optimal tour, in the worst case over all possible instances. We prove (almost) tight bounds on this quantity for a special 1-dimensional scenario and for general metric spaces. We believe that the Price-of-Diversity framework that we introduce is interesting in its own right, and may lead to follow-up work on other problems as well.

KW - Diverse Solutions

KW - Path TSP

KW - Price of Diversity

KW - TSP

UR - https://www.scopus.com/pages/publications/105031306203

U2 - 10.1007/978-981-95-7127-7_27

DO - 10.1007/978-981-95-7127-7_27

M3 - Conference contribution

AN - SCOPUS:105031306203

SN - 978-981-95-7126-0

T3 - Lecture Notes in Computer Science (LNCS)

SP - 402

EP - 417

BT - WALCOM: Algorithms and Computation

A2 - Di Giacomo, Emilio

A2 - Mondal, Debajyoti

PB - Springer

CY - Singapore

T2 - 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026

Y2 - 4 March 2026 through 6 March 2026

ER -

de Berg M , López Martínez A , Spieksma F. Disjoint Tours and the Price of Diversity. In Di Giacomo E, Mondal D, editors, WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings. Singapore: Springer. 2026. p. 402-417. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-981-95-7127-7_27