Tullio Villa

An Asymptotic Framework for the Integrality Gap of the Traveling Salesman Problem

Categories 0-1 Programming, Linear Programming Tags , ,

The integrality gap of the subtour elimination relaxation for the Traveling Salesman Problem is a longstanding open problem, epitomized by the \(\frac{4}{3}\)-conjecture. Understanding this gap requires a detailed analysis of the extreme points of the subtour elimination polytope. In this work, we introduce a new perspective for studying the integrality gap through what we call … Read more

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

Categories 0-1 Programming, Linear Programming, Polyhedra Tags , ,

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 … Read more