Improving on best-of-many-Christofides for \(T\)-tours

DOI10.1016/j.orl.2020.09.009OpenAlexW3090361369MaRDI QIDQ2661569

Vera Traub

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmtraveling salesman problem\(T\)-joinintegrality gap

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Related Items (1)

Reducing Path TSP to TSP

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
• A construction for binary matroids
• Analysis of Christofides' heuristic: some paths are more difficult than cycles
• Better \(s-t\)-tours by Gao trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• An improved upper bound on the integrality ratio for the \(s\)-\(t\)-path TSP
• Approximating minimum-cost connected \(T\)-joins
• Layers and matroids for the traveling salesman's paths
• Slightly improved upper bound on the integrality ratio for the \(s - t\) path TSP
• Reassembling Trees for the Traveling Salesman
• Improving Christofides' Algorithm for the s-t Path TSP
• Heuristic analysis, linear programming and branch and bound
• A new approach to the minimum cut problem
• Computing All Small Cuts in an Undirected Network
• Matching, Euler tours and the Chinese postman
• Eight-Fifth Approximation for the Path TSP
• Reducing path TSP to TSP
• Suboptimal cuts: Their enumeration, weight and number
• The Salesman’s Improved Paths through Forests
• A 1.5-Approximation for Path TSP
• Approaching 3/2 for the s - t -path TSP
• Minimum cuts in near-linear time

This page was built for publication: Improving on best-of-many-Christofides for \(T\)-tours