Disjoint Tours and the Price of Diversity

2025/07/17 by Mark de Berg, de Berg, Mark, Andrés López Martínez +3
Decision Sciences · #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2507.13026

openalex publication_date 2025/07/17 · openalex created_date 2025/10/18 · openalex updated_date 2026/08/01

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.

Citations

• Finding Diverse Strings and Longest Common Subsequences in a Graph
• Balancing Notions of Equity: Trade-offs Between Fair Portfolio Sizes and Achievable Guarantees
• Finding Diverse Minimum s-t Cuts
• The Two-Squirrel Problem and Its Relatives
• DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems
• Diversity-aware k-median : Clustering with fair center representation
• Diverse Pairs of Matchings
• Finding Diverse Trees, Paths, and More
• Multiwinner Elections with Diversity Constraints
• k-best enumeration

Related

• An Analysis of Several Heuristics for the Traveling Salesman Problem
• The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components
• On the Nearest Neighbor Rule for the Metric Traveling Salesman Problem
• Counting Locally Optimal Tours in the TSP
• Balanced TSP partitioning