On the Metric $s$--$t$ Path Traveling Salesman Problem

DOI10.1137/17M1161257zbMath1397.90326MaRDI QIDQ4641715

Zhihan Gao

Publication date: 18 May 2018

Published in: SIAM Review (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmslinear programming relaxationspath traveling salesman problem

Mathematics Subject Classification ID

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

Uses Software

• Concorde

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
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• On a theorem of Mader
• The parsimonious property of cut covering problems and its applications
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Worst-case analysis of a new heuristic for the travelling salesman problem
• 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
• Reassembling Trees for the Traveling Salesman
• Approximating Minimum-Cost Connected T-Joins
• Finding the Exact Integrality Gap for Small Traveling Salesman Problems
• Better s-t-Tours by Gao Trees
• Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP
• Eight-Fifth Approximation for the Path TSP
• Improving christofides' algorithm for the s-t path TSP
• On the Metric $s$--$t$ Path Traveling Salesman Problem

This page was built for publication: On the Metric $s$--$t$ Path Traveling Salesman Problem