arXiv preprint ·
Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Online Batching with Lookahead: Adversarial Limits and Stochastic Gains
Improved Combinatorial Auctions with and without Samples
QPTAS for Max Weight Independent Set in Graphs with Strongly Edge-Sublinear Separators
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for Ranking
Stochastic Weighted Caching with Per-Request Predictions
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.