Better \(s-t\)-tours by Gao trees

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

zbMATH Keywords

convex combinationapproximation algorithmspanning treetraveling salesman problem\(T\)-join

Mathematics Subject Classification ID

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