Better \(s-t\)-tours by Gao trees
From MaRDI portal
Publication:1800996
DOI10.1007/s10107-017-1202-zzbMath1406.90105OpenAlexW2765549233MaRDI QIDQ1800996
Jens Vygen, Corinna Gottschalk
Publication date: 26 October 2018
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-017-1202-z
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Combinatorics in computer science (68R05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (10)
A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ Beating the Integrality Ratio for $s$-$t$-Tours in Graphs ⋮ The salesman's improved tours for fundamental classes ⋮ An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP ⋮ Reducing Path TSP to TSP ⋮ An Improved Approximation Algorithm for The Asymmetric Traveling Salesman Problem
Cites Work
- 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
- Testing membership in matroid polyhedra
- 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
- An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem
- An LP-based \(\frac{3}{2}\)-approximation algorithm for the \(s-t\) path graph traveling salesman problem
- Reassembling Trees for the Traveling Salesman
- Improving Christofides' Algorithm for the s-t Path TSP
- Approaching $\frac{3}{2}$ for the $s$-$t$-path TSP
- Matching, Euler tours and the Chinese postman
- Eight-Fifth Approximation for the Path TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
This page was built for publication: Better \(s-t\)-tours by Gao trees