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…