On the Metric $s$--$t$ Path Traveling Salesman Problem
From MaRDI portal
Publication:5499730
DOI10.1137/14096712XzbMath1331.68293arXiv1404.7569OpenAlexW2802283659MaRDI QIDQ5499730
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
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Related Items (7)
Better s-t-Tours by Gao Trees ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem ⋮ 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
Cites Work
- 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
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Approximating Minimum-Cost Connected T-Joins
- Finding the Exact Integrality Gap for Small Traveling Salesman Problems
- Eight-Fifth Approximation for the Path TSP
- Improving christofides' algorithm for the s-t path TSP
This page was built for publication: On the Metric $s$--$t$ Path Traveling Salesman Problem
