15 citations · 20 across the 16 of their papers we have counts for
6 papers · 1 filter
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…
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 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…
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…
Computational complexity of sum-of-squares bounds for copositive programs
Marilena Palomba, Lucas Slot, Luis Felipe Vargas +1
In recent years, copositive programming has received significant attention for its ability to model hard problems in both discrete and continuous optimization. Several relaxations…