On the metric s-t path traveling salesman problem

DOI10.1137/14096712XMaRDI QIDQ5499730zbMATH OpenOpenAlexFDO

Authors Zhihan Gao

Publication date 31 July 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmslinear programming relaxationspath traveling salesman problem

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Combinatorial optimization (90C27)

Abstract: We study the metric $s$-$t$ path Traveling Salesman Problem (TSP). [An, Kleinberg, and Shmoys, STOC 2012] improved on the long standing $frac53$-approximation factor and presented an algorithm that achieves an approximation factor of $frac1+sqrt52approx1.61803$. Later [SebH{o}, IPCO 2013] further improved the approximation factor to $frac85$. We present a simple, self-contained analysis that unifies both results; our main contribution is a emph{unified correction vector}. We compare two different linear programming (LP) relaxations of the $s$-$t$ path TSP, namely, the path version of the Held-Karp LP relaxation for TSP and a weaker LP relaxation, and we show that both LPs have the same (fractional) optimal value. Also, we show that the minimum-cost of integral solutions of the two LPs are within a factor of $frac32$ of each other. We prove that a half-integral solution of the stronger LP-relaxation of cost $c$ can be rounded to an integral solution of cost at most $frac32c$. Additionally, we give a bad instance that presents obstructions to two obvious methods that aim for an approximation factor of $frac32$.

Recommendations

• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Improving Christofides' algorithm 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
• Approaching 23 for the s-t-path TSP

Cites work

• An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximating minimum-cost connected \(T\)-joins
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Eight-fifth approximation for the path TSP
• Finding the exact integrality gap for small traveling salesman problems
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 1953187 (Why is no real title available?)
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP
• On a theorem of Mader
• 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
• The parsimonious property of cut covering problems and its applications
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(10)

• Better \(s-t\)-tours by Gao trees
• A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality
• Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
• Reassembling trees for the traveling salesman
• On the Complexity of the Metric TSP under Stability Considerations
• Improving Christofides' algorithm for the s-t path TSP
• Better s-t-tours by Gao trees
• The unbounded integrality gap of a semidefinite relaxation of the traveling salesman problem
• On the Metric $s$--$t$ Path Traveling Salesman Problem
• Improving Christofides' algorithm for the \(s\)-\(t\) path TSP

This page was built for publication: On the metric \(s\)-\(t\) path traveling salesman problem

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