Reducing path TSP to TSP

DOI10.1145/3357713.3384256MaRDI QIDQ5144892zbMATH OpenOpenAlexFDO

Authors Vera Traub, Jens Vygen, Rico Zenklusen

Publication date 19 January 2021

Published in Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1907.10376

zbMATH Keywords

approximation algorithmsdynamic programmingtraveling salesman problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Dynamic programming (90C39)

Abstract: We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an $alpha$-approximation algorithm for TSP, then, for any $epsilon>0$, there is an $(alpha+epsilon)$-approximation algorithm for the more general Path TSP. This reduction implies that the approximability of Path TSP is the same as for TSP, up to an arbitrarily small error. This avoids future discrepancies between the best known approximation factors achievable for these two problems, as they have existed until very recently. A well-studied special case of TSP, Graph TSP, asks for tours in unit-weight graphs. Our reduction shows that any $alpha$-approximation algorithm for Graph TSP implies an $(alpha+epsilon)$-approximation algorithm for its path version. By applying our reduction to the $1.4$-approximation algorithm for Graph TSP by SebH{o} and Vygen, we obtain a polynomial-time $(1.4+epsilon)$-approximation algorithm for Graph Path TSP, improving on a recent $1.497$-approximation algorithm of Traub and Vygen. We obtain our results through a variety of new techniques, including a novel way to set up a recursive dynamic program to guess significant parts of an optimal solution. At the core of our dynamic program we deal with instances of a new generalization of (Path) TSP which combines parity constraints with certain connectivity requirements. This problem, which we call $Phi$-TSP, has a constant-factor approximation algorithm and can be reduced to TSP in certain cases when the dynamic program would not make sufficient progress.

Recommendations

• A 1.5-approximation for path TSP
• Approaching 23 for the s-t-path TSP
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Improving Christofides' algorithm for the s-t path TSP

Cited in

(13)

• Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
• Improving on best-of-many-Christofides for \(T\)-tours
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• A 1.5-approximation for path TSP
• Reducing Path TSP to TSP
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• A deterministic better-than-3/2 approximation algorithm for metric TSP
• Polyhedral techniques in combinatorial optimization: matchings and tours
• Travelling salesman paths on Demidenko matrices
• Approximation algorithms for graph search problems with imperfect detection
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• Graph spanners for group Steiner distances
• Approximating prize-collecting variants of tsp

This page was built for publication: Reducing path TSP to TSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144892)