Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. For the min-knapsack cover problem, our main result can be stated formally as follows: for any epsilon > 0, there is a (1/epsilon)(o(1))n(o(log n))- size LP relaxation with an integrality gap of at most 2 +epsilon, where n is the number of items. Previously, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our techniques are also sufficiently versatile to give analogous results for the closely related flow cover inequalities that are used to strengthen relaxations for scheduling and facility location problems.