Reassembling Trees for the Traveling Salesman
From MaRDI portal
Publication:2806177
DOI10.1137/15M1010531zbMath1345.90079arXiv1502.03715MaRDI QIDQ2806177
Publication date: 17 May 2016
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1502.03715
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items (12)
A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Better s-t-Tours by Gao Trees ⋮ Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP ⋮ Improving on best-of-many-Christofides for \(T\)-tours ⋮ An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ An LP-based approximation algorithm for the generalized traveling salesman path problem ⋮ On the Metric $s$--$t$ Path Traveling Salesman Problem ⋮ A 4-approximation algorithm for the TSP-path satisfying a biased triangle inequality ⋮ Better \(s-t\)-tours by Gao trees ⋮ 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
- 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
- Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem
- \(\frac{13}{9}\)-approximation for graphic TSP
- 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
- New Inapproximability Bounds for TSP
- Better s-t-Tours by Gao Trees
- Heuristic analysis, linear programming and branch and bound
- Matching, Euler tours and the Chinese postman
- Eight-Fifth Approximation for the Path TSP
- Solution of a Large-Scale Traveling-Salesman Problem
- Improving christofides' algorithm for the s-t path TSP
- A Randomized Rounding Approach to the Traveling Salesman Problem
- Approximating Graphic TSP by Matchings
- On the Metric $s$--$t$ Path Traveling Salesman Problem
- The Traveling-Salesman Problem and Minimum Spanning Trees
This page was built for publication: Reassembling Trees for the Traveling Salesman