The salesman's improved tours for fundamental classes

DOI10.1007/S10107-019-01455-3zbMath1459.90175arXiv1705.02385OpenAlexW2993020359MaRDI QIDQ2227538

András Sebő, Sylvia Boyd

Publication date: 15 February 2021

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

TSPlinear programmingapproximationcubic graphsintegrality gap

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP ⋮ Towards improving Christofides algorithm on fundamental classes by gluing convex combinations of tours ⋮ Matroid-based TSP rounding for half-integral solutions ⋮ Efficient constructions of convex combinations for 2-edge-connected subgraphs on fundamental classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• 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
• Analyzing the Held-Karp TSP bound: A monotonicity property with application
• Better \(s-t\)-tours by Gao trees
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• On the Held-Karp relaxation for the asymmetric and symmetric traveling salesman problems
• Worst-case comparison of valid inequalities for the TSP
• Finding 2-Factors Closer to TSP Tours in Cubic Graphs
• Finding the Exact Integrality Gap for Small Traveling Salesman Problems
• Cycles Intersecting Edge-Cuts of Prescribed Sizes
• Greedy algorithm and symmetric matroids
• Heuristic analysis, linear programming and branch and bound
• Spanning trees with many or few colors in edge-colored graphs
• Delta-Matroids, Jump Systems, and Bisubmodular Polyhedra
• Matching, Euler tours and the Chinese postman
• 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
• A Randomized Rounding Approach to the Traveling Salesman Problem

This page was built for publication: The salesman's improved tours for fundamental classes