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 (Corresponderende auteur)
, Frits Spieksma

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

Samenvatting

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.

Originele taal-2	Engels
Titel	WALCOM: Algorithms and Computation
Subtitel	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings
Redacteuren	Emilio Di Giacomo, Debajyoti Mondal
Plaats van productie	Singapore
Uitgeverij	Springer
Pagina's	402-417
Aantal pagina's	16
ISBN van elektronische versie	978-981-95-7127-7
ISBN van geprinte versie	978-981-95-7126-0
DOI's	https://doi.org/10.1007/978-981-95-7127-7_27
Status	Gepubliceerd - 14 feb. 2026
Evenement	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026 - Perugia, Italië Duur: 4 mrt. 2026 → 6 mrt. 2026

Publicatie series

Naam	Lecture Notes in Computer Science (LNCS)
Volume	16444
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026
Land/Regio	Italië
Stad	Perugia
Periode	4/03/26 → 6/03/26

Bibliografische nota

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

Toegang tot document

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

Andere bestanden en links

Link naar publicatie in Scopus

Document onder embargo

pdf
Definitieve gepubliceerde versie, 477 KB
Licentie: TAVERNE
Embargo eindigt: 14/08/26

Citeer dit

de Berg, M., López Martínez, A., & Spieksma, F. (2026). Disjoint Tours and the Price of Diversity. In E. Di Giacomo, & D. Mondal (editors), WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings (blz. 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. redacteur / Emilio Di Giacomo ; Debajyoti Mondal. Singapore : Springer, 2026. blz. 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 (reds.), 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, blz. 402-417, 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italië, 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 (Corresponderende auteur); Spieksma, Frits.
WALCOM: Algorithms and Computation: 20th International Conference and Workshops on Algorithms and Computation, WALCOM 2026, Perugia, Italy, March 4–6, 2026, Proceedings. reds. / Emilio Di Giacomo; Debajyoti Mondal. Singapore: Springer, 2026. blz. 402-417 (Lecture Notes in Computer Science (LNCS); Vol. 16444).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, 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. blz. 402-417. (Lecture Notes in Computer Science (LNCS)). doi: 10.1007/978-981-95-7127-7_27