Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2507.13026 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917097797320704 |
|---|---|
| author | de Berg, Mark Martínez, Andrés López Spieksma, Frits |
| author_facet | de Berg, Mark Martínez, Andrés López Spieksma, Frits |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_13026 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Disjoint Tours and the Price of Diversity de Berg, Mark Martínez, Andrés López Spieksma, Frits Data Structures and Algorithms 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. |
| title | Disjoint Tours and the Price of Diversity |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.13026 |