The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+6 Non-zero Components

2025/07/09 by Villa, Tullio, Eleonora Vercesi, Vercesi, Eleonora +4 · 2 voices
Computer Science · Engineering · #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Vehicle Routing Optimization Methods

paper · pdf · doi:10.48550/arxiv.2507.07003

openalex publication_date 2025/07/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We address the classical Dantzig - Fulkerson - Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution has at most n + 6 non-zero components, then the conjecture is true. To establish this result, we devise a new methodology that combines theoretical analysis and computational verification.

Citations

• Dual Charging for Half-Integral TSP
• A 4/3-Approximation Algorithm for Half-Integral Cycle Cut Instances of the TSP
• Matroid-Based TSP Rounding for Half-Integral Solutions
• On the generation of Metric TSP instances with a large integrality gap by branch-and-cut
• A (Slightly) Improved Approximation Algorithm for Metric TSP
• An Improved Approximation Algorithm for TSP in the Half Integral Case
• The Salesman's Improved Tours for Fundamental Classes
• On the Integrality Ratio of the Subtour LP for Euclidean TSP

Discussions

• ✨ We show the integrality gap for the symmetric TSP is ≤ 4/3 when the LP solution has ≤ n+6 nonzeros. 💻 After a careful study of the TSP polytope, we reduce the problem to finitely many cases and ana [bsky, 7 points, 0 comments]
• Tullio Villa, Eleonora Vercesi, Janos Barta, Monaldo Mastrolilli: The Integrality Gap of the Traveling Salesman Problem is $4/3$ if the LP Solution Has at Most $n+6$ Non-zero Components https://arxiv. [bsky, 0 points, 0 comments]

Related

• On the Integrality Gap of the Subtour LP for the 1,2-TSP
• Characterizing the Integrality Gap of the Subtour LP for the Circulant\n Traveling Salesman Problem
• The Salesman's Improved Tours for Fundamental Classes
• An Improved Approximation Algorithm for TSP in the Half Integral Case
• Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps