Approaching 23 for the s-t-path TSP

zbMATH Open1403.68355arXiv1707.03992MaRDI QIDQ4608010FDOQ4608010

Authors: Vera Traub, Jens Vygen 

Publication date: 15 March 2018

Abstract: We show that there is a polynomial-time algorithm with approximation guarantee $frac32+epsilon$ for the $s$-$t$-path TSP, for any fixed $epsilon>0$. It is well known that Wolsey's analysis of Christofides' algorithm also works for the $s$-$t$-path TSP with its natural LP relaxation except for the narrow cuts (in which the LP solution has value less than two). A fixed optimum tour has either a single edge in a narrow cut (then call the edge and the cut lonely) or at least three (then call the cut busy). Our algorithm "guesses" (by dynamic programming) lonely cuts and edges. Then we partition the instance into smaller instances and strengthen the LP, requiring value at least three for busy cuts. By setting up a $k$-stage recursive dynamic program, we can compute a spanning tree $(V,S)$ and an LP solution $y$ such that $(frac12+O(2^{-k}))y$ is in the $T$-join polyhedron, where $T$ is the set of vertices whose degree in $S$ has the wrong parity.

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

Recommendations

• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• A 1.5-approximation for path TSP

Mathematics Subject Classification ID

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

Cited In (18)

• A 1.5-approximation for path TSP
• Approximating minimum-cost connected \(T\)-joins
• Approaching 3/2 for the \(s\)-\(t\)-path TSP
• The salesman's improved paths through forests
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
• Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
• Better \(s-t\)-tours by Gao trees
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• On the metric \(s\)-\(t\) path traveling salesman problem
• Better \(s\)-\(t\)-tours by Gao trees
• Algorithms for Euclidean degree bounded spanning tree problems
• An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
• Layers and matroids for the traveling salesman's paths
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Reducing path TSP to TSP

This page was built for publication: Approaching \(\frac 23\) for the \(s\)-\(t\)-path TSP

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