Improved approximation algorithms for multi-depot and multi-path graphic TSP
Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP
Data Structures and Algorithms
Summary
The paper addresses two traveling salesperson problems on networks where routes must connect multiple starting points or follow multiple paths. For the multi-depot version, it improves a known method to efficiently find routes connecting all points to any one of several depots, with better running time and approximation quality. For the multi-path version, the paper improves the guaranteed quality of a known method that finds paths covering all points. The authors apply advanced graph techniques to make these improvements.
What this means in practice
- •For logistics planners: More efficiently compute near-optimal routes connecting multiple depots to delivery points in network-constrained settings.
- •For network infrastructure teams: Design better routes that connect various nodes through multiple paths with improved guarantees on total travel cost.
Authors
Niklas Dahlmeier, Raoul Luqué, Philipp Pabst, Laura Vargas Koch
Abstract
We give improved approximation algorithms for two graphic TSP variants. First, we consider Multi-Depot TSP on graphic instances. In this variant, we are given an undirected graph with a set of depot vertices, and we are tasked with finding an Eulerian multi-edge set that connects each non-depot vertex to at least one depot. For this problem, Deppert, Kaul and Mnich (ESA 2023) presented a 3/2-approximation algorithm with running time exponential in the number of depots. We improve this result to a fully polynomial 3/2-approximation. Our algorithm is a variant of the classic Christofides-Serdyukov algorithm with an improved and simple analysis. On subcubic instances, we improve the approximation guarantee to 4/3 using the technique of removable pairings introduced by Mömke and Svensson (J. ACM 2016). We use a removable pairing to construct a set of disjoint cycles that can be completed to a cheap feasible solution. Second, we consider the Graphic Multi-Path TSP, which was previously considered by Alimi, Dahlmeier, Mömke, Pabst and Vargas Koch (SOSA 2026) who give a 2-approximation for this problem. Additionally, the authors present a reduction that shows that any better-than-two approximation for Graphic Multi-Depot TSP immediately leads to an improvement for Graphic Multi-Path TSP. We give an improved algorithm and analysis that yield an approximation guarantee of 1.9304.