8 citations · 8 across the 7 of their papers we have counts for
9 papers
Integrality gap preserving reductions
Koppány István Encz, Monaldo Mastrolilli, Eleonora Vercesi
We propose a framework for the systematic study of integrality gaps of combinatorial optimization problems with respect to a fixed linear programming formulation. The method, calle…
TSP with Predictions: Heatmap to Tour with Provable Guarantees
Marek Eliáš, Fabrizio Grandoni, Adam Polak +1
The Traveling Salesperson Problem (TSP) has long served as a benchmark for evaluating the strength of optimization techniques in the classical theory of algorithms. In recent effor…
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…
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…
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…
A kinetic description of the body size distributions of species
Stefano Gualandi, Giuseppe Toscani, Eleonora Vercesi
In this paper, by resorting to classical methods of statistical mechanics, we build a kinetic model able to reproduce the observed statistical weight distribution of many diverse s…
On the generation of Metric TSP instances with a large integrality gap by branch-and-cut
Eleonora Vercesi, Stefano Gualandi, Monaldo Mastrolilli +1
This paper introduces a computational method for generating metric Travelling Salesman Problem (TSP) instances having a large integrality gap. The method is based on the solution o…
The Gene Mover's Distance: Single-cell similarity via Optimal Transport
Riccardo Bellazzi, Andrea Codegoni, Stefano Gualandi +2
This paper introduces the Gene Mover's Distance, a measure of similarity between a pair of cells based on their gene expression profiles obtained via single-cell RNA sequencing. Th…