A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP

DOI10.1007/978-3-031-32726-1_16zbMath1529.90068arXiv2211.04639OpenAlexW4377200021MaRDI QIDQ6086003

David P. Williamson, Nathan Klein, Billy Jin

Publication date: 9 November 2023

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

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

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Finding low cost TSP and 2-matching solutions using certain half-integer subtour vertices
• Matroid-based TSP rounding for half-integral solutions
• The salesman's improved tours for fundamental classes
• Removing and Adding Edges for the Traveling Salesman Problem
• Heuristic analysis, linear programming and branch and bound
• An improved approximation algorithm for TSP in the half integral case
• 2-Matchings, the Traveling Salesman Problem, and the Subtour LP: A Proof of the Boyd-Carr Conjecture
• Solution of a Large-Scale Traveling-Salesman Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• A (slightly) improved approximation algorithm for metric TSP

This page was built for publication: A 4/3-approximation algorithm for half-integral cycle cut instances of the TSP