摘要：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 quasipolynomial
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 ε > 0, there is a (1/ε)
O(1)n
O(logn)
-size LP relaxation with an integrality gap of at
most 2+ε, 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.
关键词：extended formulations; communication complexity; linear programming;;
knapsack
