The Integrality Gap of the Traveling Salesman Problem is $\frac{4}{3}$ if the LP Solution Has at Most $n + 6$ Non-Zero Components
- 13 June 2026
- book chapter
- Published by Springer Nature
- p. 128-143
Abstract
No abstract availableKeywords
All Related Versions
This publication has 20 references indexed in Scilit:
- A $\frac{4}{3}$-approximation algorithm for half-integral cycle cut instances of the TSPMathematical Programming, 2025
- Matroid-based TSP rounding for half-integral solutionsMathematical Programming, 2024
- On the generation of metric TSP instances with a large integrality gap by branch-and-cutMathematical Programming Computation, 2023
- Hard to solve instances of the Euclidean Traveling Salesman ProblemMathematical Programming Computation, 2020
- The salesman’s improved tours for fundamental classesMathematical Programming, 2019
- TSP on Cubic and Subcubic GraphsLecture Notes in Computer Science, 2011
- Worst-case comparison of valid inequalities for the TSPMathematical Programming, 1995
- Optimizing over the subtour polytope of the travelling salesman problemMathematical Programming, 1990
- The traveling salesman problem on a graph and some related integer polyhedraMathematical Programming, 1985
- Heuristic analysis, linear programming and branch and bound1980