Theory of Computing
-------------------
Title : Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits
Authors : Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
Volume : 14
Number : 14
Pages : 1-29
URL : https://theoryofcomputing.org/articles/v014a014
Abstract
--------
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.
Our construction is inspired by a connection between extended
formulations and monotone circuit complexity via Karchmer-Wigderson
games. In particular, our LP is based on $O(\log^2 n)$-depth monotone
circuits with fan-in $2$ for evaluating weighted threshold functions
with $n$ inputs, as constructed by Beimel and Weinreb. We believe that
a further understanding of this connection may lead to more positive
results complementing the numerous lower bounds recently proved for
extended formulations.
A conference version of this paper appeared in the
Proceedings of the 28th ACM-SIAM Symposium on
Discrete Algorithms (SODA 2017).