Eight-fifth approximation for the path TSP

DOI10.1007/978-3-642-36694-9_31MaRDI QIDQ4911537zbMATH OpenOpenAlexFDO

Authors András Sebö

Publication date 19 March 2013

Published in Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

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

zbMATH Keywords

\(T\)-joinapproximation algorithmmatchingpath TSPpolyhedrontraveling salesman problemtree (basis) polytope

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We prove the approximation ratio 8/5 for the metric $s,t$-path-TSP problem, and more generally for shortest connected $T$-joins. The algorithm that achieves this ratio is the simple "Best of Many" version of Christofides' algorithm (1976), suggested by An, Kleinberg and Shmoys (2012), which consists in determining the best Christofides $s,t$-tour out of those constructed from a family $Fsc{r}_{>0}$ of trees having a convex combination dominated by an optimal solution $x^{\ast }$ of the fractional relaxation. They give the approximation guarantee $fracsqrt5+12$ for such an $s,t$-tour, which is the first improvement after the 5/3 guarantee of Hoogeveen's Christofides type algorithm (1991). Cheriyan, Friggstad and Gao (2012) extended this result to a 13/8-approximation of shortest connected $T$-joins, for $|T|ge4$. The ratio 8/5 is proved by simplifying and improving the approach of An, Kleinberg and Shmoys that consists in completing $x^{\ast }/2$ in order to dominate the cost of "parity correction" for spanning trees. We partition the edge-set of each spanning tree in $Fsc{r}_{>0}$ into an $s,t$-path (or more generally, into a $T$-join) and its complement, which induces a decomposition of $x^{\ast }$. This decomposition can be refined and then efficiently used to complete $x^{\ast }/2$ without using linear programming or particular properties of $T$, but by adding to each cut deficient for $x^{\ast }/2$ an individually tailored explicitly given vector, inherent in $x^{\ast }$. A simple example shows that the Best of Many Christofides algorithm may not find a shorter $s,t$-tour than 3/2 times the incidentally common optima of the problem and of its fractional relaxation.

Recommendations

• Improving Christofides' algorithm for the s-t path TSP
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• Approximating minimum-cost connected \(T\)-joins
• The salesman's improved paths through forests
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs

Cited in

(30)

• Better \(s-t\)-tours by Gao trees
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• Approximation algorithms for general cluster routing problem
• Approximation algorithms with constant ratio for general cluster routing problems
• A LP-based approximation algorithm for generalized traveling salesperson path problem
• \(\frac{13}{9}\)-approximation for graphic TSP
• An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
• Approximating minimum-cost connected \(T\)-joins
• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
• Improving on best-of-many-Christofides for \(T\)-tours
• An LP-based approximation algorithm for the generalized traveling salesman path problem
• Reassembling trees for the traveling salesman
• On the clustered Steiner tree problem
• Approximating minimum-cost connected \(T\)-joins
• Better s-t-tours by Gao trees
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• TSP tours in cubic graphs: beyond 4/3
• On the metric \(s\)-\(t\) path traveling salesman problem
• Reducing Path TSP to TSP
• An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
• scientific article; zbMATH DE number 7765379 (Why is no real title available?)
• Constant-factor approximation algorithms for parity-constrained facility location and \(k\)-center
• Beating the Integrality Ratio for $s$-$t$-Tours in Graphs
• Stability of Reapproximation Algorithms for the $$\beta $$-Metric Traveling Salesman (Path) Problem
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• 1.6-approximation algorithm for generalized traveling salesman path problem
• Approximation algorithms for the bus evacuation problem

This page was built for publication: Eight-fifth approximation for the path TSP

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