An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem

DOI10.1016/j.orl.2013.08.006zbMath1287.90053OpenAlexW1971797008MaRDI QIDQ2450741

Zhihan Gao

Publication date: 15 May 2014

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2013.08.006

zbMATH Keywords

linear programmingapproximation algorithms\(s-t\) path traveling salesman problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Combinatorial optimization (90C27)

Related Items (10)

Better s-t-Tours by Gao Trees ⋮ Layers and matroids for the traveling salesman's paths ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Reassembling Trees for the Traveling Salesman ⋮ Better \(s-t\)-tours by Gao trees ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes ⋮ Reducing Path TSP to TSP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 ellipsoid method and its consequences in combinatorial optimization
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Approximating Minimum-Cost Connected T-Joins
• Eight-Fifth Approximation for the Path TSP
• Improving christofides' algorithm for the s-t path TSP
• Approximating Graphic TSP by Matchings

This page was built for publication: An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem