On the Metric $s$--$t$ Path Traveling Salesman Problem
From MaRDI portal
Publication:4641715
DOI10.1137/17M1161257zbMath1397.90326MaRDI QIDQ4641715
Publication date: 18 May 2018
Published in: SIAM Review (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)
Uses Software
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