BIRS Workshop Lecture Videos
Bounded pitch inequalities for min knapsack: approximate separation and integrality gaps Faenza, Yuri
The pitch of a (valid) inequality for the min knapsack polytope is the minimum integer k such that, if any k variables from its support are set to one, then the inequality is satisfied. Bounded pitch inequalities came to prominence for their connections with the Chvatal-Gomory and Bienstock-Zuckerberg operators. In this talk, we investigate the strength of bounded pitch inequalities, proving bounds on the integrality gap when they are added to the natural LP relaxation (possibly, in conjunction with other inequalities), and we discuss algorithms for approximately separating them.
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International