BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Bounded pitch inequalities for min knapsack: approximate separation and integrality gaps Faenza, Yuri

Description

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 Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International