The IDSIA Work-In-Progress is a permanent series of internal seminars designed as a space for the IDSIA USI-SUPSI young researchers to present their work and share preliminary results of their ongoing research projects. In an expanding reality such as IDSIA USI-SUPSI, the WIP is intended to be an opportunity for the members of the institute to get to know each other and to present themselves to the rest of the community, as well as to increase internal networking and foster exchanges and collaborations. Various talks are offered throughout the year, every two or three weeks, depending on the availability of the speakers. The attendance is open to all members of the institute.
Each seminar lasts approximately 40 minutes (talk + Q&A), followed by a moment of informal conviviality with tea and biscuits.
If you are young researcher at IDSIA USI-SUPSI interested to present your work in the WIP series, please compile the following form.
09.06.2026
h. 17.00
Room B1.07
Tullio Villa
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.
During this event, photos will be taken and may be published on our website in compliance with Swiss data protection laws