Abstract: The Traveling Salesman Problem (TSP) is one of the most extensively studied combinatorial optimization problems, with its linear programming (LP) formulation playing a central role in approximation algorithms. A fundamental open question concerns the ratio between the optimal integral solution and its LP relaxation, known as the integrality gap. Notably, the "4/3-conjecture" drives this investigation, stating that such a ratio can not be worse than 4/3. Understanding the integrality gap requires a detailed analysis of the structure of fractional solutions, especially the extreme points of the associated polytope. In this work, we introduce a new perspective for studying the integrality gap through what we call the "Asymptotic Framework". Rather than focusing on individual vertices, we consider entire families of vertices and analyze their behavior in the limit. This approach allows us to capture structural properties that might otherwise remain hidden at the level of isolated instances. We develop tools for systematically constructing and analyzing such families, and we demonstrate how this framework yields new insights into the broader study of the integrality gap.

Short bio: Tullio Villa is a PhD student in Informatics at IDISA USI-SUPSI, where he works in the Optimization & Complexity group under the supervision of Prof. Mastrolilli and Prof. Gambardella. He obtained his Bachelor's and Master's degree in Mathematics at Universita' degli Studi di Milano. His research focuses primarily on polyhedral combinatorics and the integrality gap of NP-Hard problems, particularly the TSP.