Better s-t-Tours by Gao Trees

DOI10.1007/978-3-319-33461-5_11zbMath1419.90094arXiv1511.05514OpenAlexW2172689705MaRDI QIDQ3186497

Jens Vygen, Corinna Gottschalk

Publication date: 10 August 2016

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1511.05514

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (6)

An experimental evaluation of the best-of-many Christofides' algorithm for the traveling salesman problem ⋮ Layers and matroids for the traveling salesman's paths ⋮ 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 ⋮ Reassembling Trees for the Traveling Salesman

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
• The ellipsoid method and its consequences in combinatorial optimization
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• 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
• Matching, Euler tours and the Chinese postman
• Eight-Fifth Approximation for the Path TSP
• Improving christofides' algorithm for the s-t 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