A

Approximation Algorithms for Graphic Multi-Depot TSP and Graphic Multi-Path TSP

arXiv (Cornell University)

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.

Authors 4

  1. RWTH Aachen University

    Affiliation as printed

    RWTH Aachen University

  2. Raoul Luqué Aachen

    RWTH Aachen University

    Affiliation as printed

    RWTH Aachen University

  3. Philipp Pabst Aachen

    RWTH Aachen University

    Affiliation as printed

    RWTH Aachen University

  4. RWTH Aachen University

    Affiliation as printed

    RWTH Aachen University

Cited by 0 stored of 0

References 16

16 results