7 papers
Branch-and-Bound Algorithms as Polynomial-time Approximation Schemes
Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
Branch-and-bound algorithms (B&B) and polynomial-time approximation schemes (PTAS) are two seemingly distant areas of combinatorial optimization. We intend to (partially) bridge th…
The Integrality Gap of the Traveling Salesman Problem is if the LP Solution Has at Most Non-zero Components
Tullio Villa, Eleonora Vercesi, Janos Barta +1
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…
On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
Alex Bortolotti, Monaldo Mastrolilli, Marilena Palomba +1
The Sum-of-Squares (SoS) hierarchy is a powerful framework for polynomial optimization and proof complexity, offering tight semidefinite relaxations that capture many classical alg…
On the integrality Gap of Small Asymmetric Traveling Salesman Problems: A Polyhedral and Computational Approach
Eleonora Vercesi, Janos Barta, Luca Maria Gambardella +2
In this paper, we investigate the integrality gap of the Asymmetric Traveling Salesman Problem (ATSP) with respect to the linear relaxation given by the Asymmetric Subtour Eliminat…
On the Degree Automatability of Sum-of-Squares Proofs
Alex Bortolotti, Monaldo Mastrolilli, Luis Felipe Vargas
The Sum-of-Squares (SoS) hierarchy, also known as Lasserre hierarchy, has emerged as a promising tool in optimization. However, it remains unclear whether fixed-degree SoS proofs c…
Lower bounds for the integrality gap of the bi-directed cut formulation of the Steiner Tree Problem
Ambrogio Maria Bernardelli, Eleonora Vercesi, Stefano Gualandi +2
In this work, we study the metric Steiner Tree problem on graphs focusing on computing lower bounds for the integrality gap of the bi-directed cut (BCR) formulation and introducing…