Authors Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29
www.theoryofcomputing.org
Small Extended Formulation for Knapsack
Cover Inequalities from Monotone Circuits
Abbas Bazzi∗ Samuel Fiorini† Sangxia Huang‡ Ola Svensson§
Received December 9, 2016; Revised August 13, 2018; Published December 2, 2018
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 ε > 0, there is a (1/ε)O(1) nO(log n) -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.
A conference version of this paper appeared in the Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms
(SODA 2017) [7].
∗ Supported in part by a SNSF Grant.
† Supported by ERC Consolidator Grant 615640-ForEFront.
‡ Supported by ERC Starting Grant 335288-OptApprox.
§ Supported by ERC Starting Grant 335288-OptApprox.
ACM Classification: G.1.6
AMS Classification: 68Q25, 90C59
Key words and phrases: extended formulations, communication complexity, linear programming,
knapsack
© 2018 Abbas Bazzi, Samuel Fiorini, Sangxia Huang, and Ola Svensson
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2018.v014a014
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
Our construction is inspired by a connection between extended formulations and mono-
tone circuit complexity via Karchmer-Wigderson games. In particular, our LP is based on
O(log2 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.
1 Introduction
Capacitated covering problems1 play a central role in combinatorial optimization. These are the problems
modeled by Integer Programs (IPs) of the form
( )
n
min ∑ ci xi Ax ⩾ b, x ∈ {0, 1}n ,
i=1
where A is a size-m × n nonnegative matrix and b and c are size-m and size-n nonnegative vectors,
respectively. The min-knapsack problem is the special case arising when there is a single covering
constraint, that is, when m = 1. This is arguably the simplest interesting capacitated covering problem.
In terms of complexity, the min-knapsack problem is well-understood: on the one hand it is weakly
NP-hard [30] and on the other hand it admits an FPTAS [31, 37]. However, for its own sake and since
it appears as a key substructure of numerous other IPs, improving our polyhedral understanding of the
problem is important. By this, we mean finding “good” linear programming (LP) relaxations for the
min-knapsack problem. Indeed, the polyhedral study of this problem has led to the development of
important tools, such as the knapsack cover inequalities, for the strengthening of LP relaxations. These
inequalities and generalizations thereof are now used in the current best known relaxations for several
combinatorial optimization problems, such as single-machine scheduling [6] and capacitated facility
location [2]. However, despite this important progress in the past, many fundamental questions remain
open even in the most basic setting.
State of the art. The feasible region of a min-knapsack instance is specified by positive item sizes
s1 , . . . , sn and a positive demand D. In this context, a vector x ∈ {0, 1}n is feasible if ∑ni=1 si xi ⩾ D. To
specify completely an instance of the min-knapsack problem, we are further given nonnegative item costs
c1 , . . . , cn . Solving the resulting instance then amounts to solving the IP
( )
n n
min ∑ ci xi ∑ si xi ⩾ D, x ∈ {0, 1}n .
i=1 i=1
The basic LP relaxation, i. e.,
( )
n n
min ∑ ci xi ∑ si xi ⩾ D, x ∈ [0, 1]n ,
i=1 i=1
1 The term “capacitated” is used in the literature to emphasize that the entries of matrix A can take any non-negative value in
contrast to the uncapacitated version where entries are Boolean.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 2
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
provides a lower bound on the optimum value that can be quite bad. More precisely, defining the
integrality gap as the supremum over all instances of the ratio of the optimum value of the IP to the
optimum value of the LP relaxation, it is easy to see that the integrality gap is unbounded.
Several inequalities have been proposed for strengthening this basic LP relaxation. Already in the
1970s, Balas [3], Hammer, Johnson and Peled [27] and Wolsey [40] independently proposed to add the
uncapacitated knapsack cover inequalities: for every subset A ⊆ [n] := {1, . . . , n} of the items such that
∑i∈A si < D, add the inequality ∑i6∈A xi ⩾ 1 (saying that at least one item in [n] \ A needs to be picked in
order to satisfy the demand). Unfortunately, these (exponentially many) inequalities are not sufficient
for bringing down the integrality gap to a constant. A strengthening of these inequalities was therefore
proposed more recently by Carr, Fleischer, Leung and Philipps [15]. They defined the following valid
inequalities: for every set of items A ⊆ [n] such that ∑i∈A si < D, there is a corresponding (capacitated)
knapsack cover inequality
∑ s0i xi ⩾ U (1.1)
i∈A
/
where U = U(A) := D − ∑i∈A si is the residual demand and s0i = s0i (A) := min{si ,U}. The validity of (1.1)
is due to the fact that every feasible solution x ∈ {0, 1}n has to contain some object i ∈/ A. This object can
be large, that is, have si ⩾ U, and in this case the inequality is clearly satisfied. Otherwise, in case every
object i ∈
/ A is small, the total size of the objects i ∈
/ A picked by x has to be at least the residual demand
U.
Carr et al. [15] proved that whenever x ∈ Rn⩾0 satisfies all knapsack cover inequalities, 2x dominates
a convex combination of feasible solutions, that is, there exist feasible solutions x( j) ∈ {0, 1}n ( j ∈ [q])
and coefficients λ j ⩾ 0 summing up to 1 such that
q
2x ⩾ ∑ λ j x( j) .
j=1
Given any nonnegative item costs, one of the x( j) will have a cost that is at most 2 times that of x. This
implies that the integrality gap of the corresponding LP relaxation is at most 2.
The LP relaxation defined by the knapsack cover inequalities is “good” in the sense that it has a
constant integrality gap. However, it has exponential size, that is, exponentially many inequalities, over
which it is not known how to optimize exactly in polynomial time; in particular, it is not known how
to employ the Ellipsoid algorithm because the problem of separating the knapsack cover inequalities
reduces to another knapsack problem (which is NP-hard in general).
In contrast, for the max-knapsack problem, Bienstock [11] proved that for all ε > 0 there exists a
size-nO(1/ε) LP relaxation whose integrality gap2 is at most 1 + ε. That LP is defined by an extended
formulation that uses nO(1/ε) extra variables besides the x-variables. We remark that it is a notorious open
problem to prove or disprove the existence of a f (1/ε) · nO(1) -size LP relaxation for max-knapsack with
integrality gap at most 1 + ε, see, e. g., Section 5.3 in the survey on extended formulations by Conforti,
Cornuéjols and Zambelli [21]. Coming back to the min-knapsack problem, it is not known whether there
exists a polynomial-size LP relaxation with constant integrality gap or not.3
2 For maximization problems, one takes the supremum of the ratio of the optimum value of the LP relaxation to the optimum
value of the IP.
3 We remark that Bienstock and McClosky [12] considered the easier case when the relaxation is allowed to depend on the
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 3
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
Main result. We come close to resolving the question and show that min-knapsack admits a quasi-
polynomial-size LP relaxation with integrality gap at most 2 + ε. Furthermore, we show that the
LP relaxation can be constructed in quasi-polynomial time whenever the data is integer and quasi-
polynomially bounded. The upper bound on the integrality gap originates from the fact that our LP
relaxation is at least as strong as that provided by a slightly weakened form of the knapsack cover
inequalities. We point out that, under some conditions, we can bound the size of our relaxation by a
polynomial, see Section 3.2. A more precise statement of our main result is as follows.
Theorem 1.1. For all given ε ∈ (0, 1), item sizes s1 , . . . , sn ∈ R+ and demand D ∈ R+ , there exists a
size-(1/ε)O(1) nO(log n) extended formulation defining an LP relaxation of min-knapsack with integrality
gap at most 2 + ε. Moreover, one can construct such an extended formulation in quasi-polynomial time
whenever 1/ε, s1 , . . . , sn and D are positive integers bounded by nO(log n) .
Our techniques are sufficiently versatile to give analogous results for the closely related flow cover
inequalities. Specifically, we show in Section 4 that adjusting our techniques to the flow cover inequalities
yields that the latter can also be approximated by a quasi-polynomial number of inequalities of roughly
the same strength. Notwithstanding their own combinatorial merit, these exponentially many inequalities
have been successfully used to strengthen relaxations for many scheduling and facility location problems.
As Theorem 1.1 is obtained by giving quasi-polynomially many inequalities of roughly the same strength
as the exponentially many cover inequalities, our techniques also lead to relaxations of quasi-polynomial
size for their numerous applications, as we discuss in the related work section.
Beyond the result itself, the novelty of our approach lies in the concepts we rely on and the techniques
we develop. Our starting point is a connection between monotone circuits and extended formulations
that we explain below. This connection was instrumental in the recent lower bounds of Göös, Jain and
Watson on the extension complexity of independent set polytopes [26], and can be traced back to a paper
of Hrubeš [28]. Here we use it for the first time to prove an upper bound.
From monotone circuits to extended formulations. Each choice of item sizes and demand gives rise
to a weighted threshold function f : {0, 1}n → {0, 1} defined as
(
1 if ∑ni=1 si xi ⩾ D ,
f (x) := (1.2)
0 otherwise.
Since we assume that the item sizes and demand are nonnegative, f is monotone in the sense that a ⩽ b
implies f (a) ⩽ f (b), for all a, b ∈ {0, 1}n .
Clearly, we have that x ∈ {0, 1}n is feasible if and only if x ∈ f −1 (1). Furthermore, for a ∈ f −1 (0),
we can rewrite the uncapacitated knapsack cover inequalities as ∑i:ai =0 xi ⩾ 1. Consider the slack
matrix Sa,b := ∑i:ai =0 bi − 1 indexed by pairs (a, b) ∈ f −1 (0) × f −1 (1). By Yannakakis’ factorization
theorem [41], the existence of a size-r LP relaxation of min-knapsack that is at least as strong as that
objective function to be optimized (i. e., on the cost of the items). In this case, using techniques similar to those developed for
polynomial-time approximation schemes, they obtained polynomial-size relaxations with integrality gap at most 1 + ε, for any
fixed ε > 0. This is, however, a very different setting and, as the developed inequalities depend on the objective function, they
do not generalize to other problems.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 4
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
given by the uncapacitated knapsack cover inequalities is equivalent to the existence of a decomposition
of the slack matrix S as a sum of r nonnegative rank-1 matrices.
Now suppose that there exists a depth-t monotone circuit (that is, using only AND gates and OR
gates) of fan-in 2 for computing f (x). A result of Karchmer and Wigderson [29] then implies a partition
of the entries of S into at most 2t rectangles4 R ⊆ f −1 (0) × f −1 (1) such that in each of these rectangles
R, there exists some index i∗ = i∗ (R) such that ai∗ = 0 and bi∗ = 1 for all (a, b) ∈ R. Then we may write,
for (a, b) ∈ R,
Sa,b = ∑ bi − 1 = ∑ bi = ∑ (1 − ai )bi (1.3)
i:ai =0 i:ai =0, i6=i∗ i6=i∗
so that S restricted to the entries of R can be expressed as a sum of at most n − 1 nonnegative rank-
1 matrices of the form ((1 − ai )bi )(a,b)∈R , where i is a fixed index distinct from i∗ . This implies a
decomposition of the whole slack matrix S as a sum of at most 2t (n − 1) nonnegative rank-1 matrices,
and thus the existence of a 2t (n − 1)-size LP relaxation of min-knapsack that captures the uncapacitated
knapsack cover inequalities. Since f is a weighted threshold function, we can take t = O(log2 n), as
proved by Beimel and Weinreb [10]. Therefore, we obtain an nO(log n) -size extended formulation for the
uncapacitated knapsack cover inequalities. Unfortunately, these inequalities do not suffice to guarantee a
bounded integrality gap.
For the full-fledged knapsack cover inequalities (1.1), the simple idea described above breaks down.
If the special index i∗ = i∗ (R) for some rectangle R corresponds to a large object, we can write
∑ s0i bi −U = ∑ s0i bi = ∑ s0i (1 − ai )bi
i:ai =0 i:ai =0, i6=i∗ i6=i∗
where each matrix (s0i (1 − ai )bi )(a,b)∈R has rank at most 1 because s0i (1 − ai ) depends on a only. However,
i∗ may correspond to a small object, in which case we cannot decompose the slack matrix as above.
Nevertheless, we prove that it is possible to overcome this difficulty. Two key ideas we use to
achieve this are to discretize some of the quantities (which explains why we lose an ε in the integrality
gap) and resort to several weighted threshold functions instead of just one. If all these functions admit
O(log n)-depth monotone circuits of fan-in 2, then we obtain a size-nO(1) LP relaxation. We remark that
it is an intriguing open problem whether general threshold functions admit O(log n)-depth monotone
circuits of fan-in 2.
Relation with other work. Knapsack cover inequalities and their generalizations such as flow cover
inequalities were used as a systematic way to strengthen LP formulations of other (seemingly unrelated)
problems [15, 14, 33, 4, 5, 16, 6, 20, 34, 19, 22]. By strengthening we mean that one would start with a
polynomial-size LP formulation with a potentially unbounded integrality gap for some problem of interest,
and then show that adding (adaptations of) knapsack cover inequalities reduces this integrality gap. As a
motivational example for the flow cover inequalities, we illustrate in Section 4 how this strengthening
works for the Single Demand Facility Location problem, reducing the integrality gap to 2. This approach
shares the same drawback that was identified in the case of min-knapsack, which is that the size of the
resulting LP formulation becomes exponential. However, our result can be extended to show that it yields
quasi-polynomial-size LP formulation for many such applications. To name a few:
4 A rectangle is the Cartesian product of a set of row indices and a set of column indices.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 5
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
• Carr et al. [15] applied these inequalities to the Generalized Vertex Cover problem, Multi-color
Network Design problem and the Fixed Charge Flow problem, and showed how these inequalities
reduce the integrality gap of the starting LP formulations.
• Efsandiari et al. [22] used a knapsack-cover-strengthened LP formulation to design an O(log k)-
approximation algorithm for Precedence-Constrained Single-Machine Deadline scheduling prob-
lem, where k is the number of distinct deadlines.
• Carnes and Shmoys [14] designed primal-dual algorithms for the Single-Demand Facility Location,
where the primal LP formulation is strengthened by adding (generalizations) of knapsack cover
inequalities.
• Bansal and Pruhs [6] studied the Generalized Scheduling Problem (GSP) that captures many
interesting scheduling problems such as Weighted Flow Time, Flow Time Squared and Weighted
Tardiness. In particular, they showed a connection between GSP and a certain geometric cov-
ering problem, and designed an LP-based approximation algorithm for the latter that yields an
approximate solution for the GSP. The LP formulation that they use for the intermediate geometric
cover problem is strengthened using knapsack cover inequalities, and yields an O(log log nP)-
approximation for the GSP where n is the number of jobs, and P is the maximum job size. In the
special case of identical release time of the jobs, their LP formulation yields a 16-approximation
algorithm. This constant-factor approximation was later improved by Cheung et al. [19] to a
(4 + ε)-approximation, where the authors added the knapsack cover inequalities directly to the LP
formulation of the scheduling problem, i. e., without resorting to the intermediate geometric cover
problem as in [6]. For both the GSP and its special case, our method yields an LP formulation
whose size is quasi-polynomial in n, and polynomial in both log P and logW , where W is the
maximum increase in the cost function of a job at any point in time. The integrality gaps achieved
by our LPs are O(log log nP) for the GSP and 4 + ε in its special case.
Extended formulations have received a considerable amount of attention recently,
√ mostly for proving
impossibility results. Pokutta and Van Vyve [38] proved a worst-case 2 Ω( n) size lower bound for
extended formulations of the max-knapsack polytope, which directly implies a similar result for the
min-knapsack polytope. Other recent articles include [25, 13, 17, 39, 32, 8].
Outline. We prove the first part of Theorem 1.1 in Section 3, after giving preliminaries in Section 2.
This is the part of Theorem 1.1 that claims the existence of an extended formulation, which is our main
contribution. In Section 3, instead of explicitly constructing our extended formulation, we provide a
nonnegative factorization of the appropriate slack matrix. For this, we use the language of communication
complexity—we give an O(log2 n+log(1/ε))-complexity two-party communication protocol with private
randomness and nonnegative outputs whose expected output is the slack of a given feasible solution with
respect to a given (weakened) knapsack cover inequality.
Next, in Section 4, we extend our communication protocol to the flow cover inequalities for the
Single-Demand Facility Location problem, and show how to approximate the exponentially many flow
cover inequalities using a smaller LP formulation.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 6
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
Finally, we use recent results of Fiorini, Huynh and Weltge [24] to show the second part of The-
orem 1.1. That is, we show how to construct in quasi-polynomial time a quasi-polynomial-size LP
formulation for min-knapsack with integrality gap at most (2 + ε). This is done in Section 5.
2 Preliminaries
In this section, we introduce some key notions related to our problem. We review extended formulations
and extension complexity of pairs of polyhedra in Section 2.1. Next, we define randomized communication
protocols with non-negative outputs that compute entries of matrices in expectation. Finally, in Section 2.3,
we review some constructions of low-depth monotone circuits, and the Karchmer-Wigderson game that
relates circuit complexity and communication complexity.
2.1 Polyhedral pairs, extended formulations and slack matrices
Let P ⊆ Rn be a polytope and Q ⊆ Rn be a polyhedron containing P. The complexity of the polyhedral
pair (P, Q) can be measured by its extension complexity, which roughly measures how compactly we can
represent a relaxation of P contained in Q. The formal definition is as follows.
Definition 2.1. Given a polyhedral pair (P, Q) where P ⊆ Q ⊆ Rn , we say that a system E ⩽ x + F ⩽ y ⩽ g⩽ ,
E = x + F = y = g= in Rn+k is an extended formulation of (P, Q) if the polyhedron
n o
R := x ∈ Rn ∃y ∈ Rk : E ⩽ x + F ⩽ y ⩽ g⩽ , E = x + F = y = g=
contains P and is contained in Q. The size of the extended formulation is the number of inequalities in
the system. The extension complexity of (P, Q), denoted by xc(P, Q), is the minimum size of an extended
formulation of (P, Q).
Although the case P = Q is probably the most frequent, we will need polyhedral pairs here. In a
seminal paper, Yannakakis [41] showed that one can study the extension complexity of a polytope P
through the non-negative rank of a matrix associated with P, namely, its slack matrix.
Definition 2.2. Let (P, Q) be a polyhedral pair with P ⊆ Q ⊆ Rn . Assume that P = conv({v1 , . . . , v p }),
where v1 , . . . , v p ∈ Rn and Q = {x ∈ Rn | Ax ⩾ b}, where A ∈ Rm×n and b ∈ Rm . We now define the
slack matrix S of the pair (P, Q) with respect to the given representations of P and Q. The ith row of S
corresponds to the constraint Ai x ⩾ bi , while the jth column of S corresponds to the point v j . The value
Si, j measures how close the constraint Ai x ⩾ bi is to being tight for point v j . More specifically, the slack
matrix S ∈ Rm×p ⩾0 is defined as Si, j := Ai v j − bi for all i ∈ [m], j ∈ [p].
Note that the slack matrix is not unique as it depends on the choices of points v1 , . . . , v p and linear
description Ax ⩾ b.
Definition 2.3. Given a non-negative matrix M ∈ Rm×n
⩾0 , we say that a pair of matrices T,U is a rank-r
non-negative factorization of M if T ∈ R⩾0 , U ∈ Rr×n
m×r
⩾0 , and M = TU. We define the non-negative
rank of M as rk+ (M) := min{r : M has a rank-r non-negative factorization}. Notice that a non-negative
factorization of M of rank at most r is equivalent to a decomposition of M as a sum of at most r
non-negative rank-1 matrices.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 7
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
Yannakakis [41] proved that for a polytope P of dimension at least 1 and any of its slack matrices S,
the extension complexity of P is equal to the non-negative rank of S, i. e., xc(P) = rk+ (S). In particular,
all the slack matrices of P have the same nonnegative rank.
This factorization theorem can be extended to polyhedral pairs: we have xc(P, Q) ∈ {rk+ (S), rk+ (S) −
1} whenever S is a slack matrix of (P, Q), see, e. g., [13].
2.2 Randomized communication protocols
We now define a certain two-party communication problem and relate it to the non-negative rank discussed
earlier, following the framework in Faenza, Fiorini, Grappe and Tiwary [23].
Definition 2.4. Let S ∈ RA×B
⩾0 be a non-negative matrix whose rows and columns are indexed by A and
B, respectively. Let Π be a communication protocol with private randomness between two players Alice
and Bob. Alice gets an input a ∈ A and Bob gets an input b ∈ B. They exchange bits in a pre-specified
way according to Π. At the end, one of the players outputs some non-negative number ξ ∈ R⩾0 . Any
of the two players is allowed to output a nonnegative number, and thus end the protocol. We say that Π
computes S in expectation if for every a and b, the expectation of the output ξ equals Sa,b .
The communication complexity of a protocol Π is the maximum of the number of bits exchanged
between Alice and Bob, over all pairs (a, b) ∈ A×B and the private randomness of the players. The size of
the final output does not count towards the communication complexity of a protocol. The communication
complexity of S, denoted Rccexp (S) is the minimum communication complexity of a randomized protocol Π
computing S in expectation.
Faenza et al. [23] relate the non-negative rank of a non-negative matrix S, to the communication
complexity Rcc cc
exp (S). In particular, they prove that if rk+ (S) 6= 0, then Rexp (S) = log2 rk+ (S) + Θ(1).
Combining this with the factorization theorem, we get Rccexp (S) = log2 xc(P, Q) + Θ(1) whenever (P, Q) is
a polyhedral pair with slack matrix S, provided that xc(P, Q) 6= 0.
2.3 Weighted threshold functions and Karchmer-Widgerson Game
An important part of our protocol depends on the communication complexity of (monotone) weighted
threshold functions. We start with the following result from [9, 10] which gives low-depth circuits
for such functions. Another construction was given in [18]. The circuits as stated in [9, 10, 18] have
logarithmic depth, polynomial size and unbounded fan-in, thus it is straightforward to convert them into
circuits with fan-in 2 with a logarithmic increase in depth. Below we state the result for circuits of fan-in
2 as will be used later. Recall that a circuit is monotone if it uses only AND and OR gates, but no NOT
gates.
Theorem 2.5 ([9, 10]). Let w1 , . . . , wn ∈ Z>0 be positive weights, and T ∈ Z⩾0 be a threshold. Let
f : {0, 1}n → {0, 1} be the monotone function such that f (x1 , . . . , xn ) = 1 if and only if ∑ni=1 wi xi ⩾ T .
Then there is a depth-O(log2 n) monotone circuit of fan-in 2 that computes the function f .
The well-known Karchmer-Wigderson game [29] connects the depth of monotone circuits and
communication complexity. Given a monotone function f : {0, 1}n → {0, 1}, the monotone Karchmer-
Wigderson game is the following: Alice receives a ∈ f −1 (0), Bob receives b ∈ f −1 (1), they communicate
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 8
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
bits to each other, and the goal is to agree on a position i ∈ {1, . . . , n} such that ai = 0 and bi = 1. Let
Dcc
mon−KW ( f ) be the deterministic communication complexity of this game.
Theorem 2.6 ([29]). Let f : {0, 1}n → {0, 1} be a monotone function, Dccmon−KW ( f ) be the deterministic
communication complexity of the Karchmer-Widgerson game, and depth( f ) be the minimum depth of a
fan-in 2 monotone circuit that computes f . Then depth( f ) = Dcc
mon−KW ( f ).
2
Combining Theorems 2.5 and 2.6, we immediately get that Dcc
mon−KW ( f ) = O(log n) for every
weighted threshold function f on n inputs.
3 Small LP relaxation for Min-Knapsack
In this section, we show the existence of a (1/ε)O(1) nO(log n) -size LP relaxation of min-knapsack with
integrality gap 2 + ε, proving Theorem 1.1. First, we give a high-level overview of the construction in
Section 3.1. The actual protocol is described and analyzed in Section 3.2.
3.1 Overview
Consider the slack matrix S that has one row for each knapsack cover inequality and one column for each
feasible solution of min-knapsack. More precisely, let f : {0, 1}n → {0, 1} denote the weighted threshold
function defined by the item sizes si (i ∈ [n]) and demand D as in (1.2). The rows and columns of S are
indexed by a ∈ f −1 (0) and b ∈ f −1 (1) respectively. The entries of S are given by
Sa,b := ∑ s0i bi −U ,
i:ai =0
where as before U = U(a) := D − ∑i:ai =1 si , and s0i = s0i (a) = min{si ,U}. Geometrically, S is the slack
matrix of the polyhedral pair (P, Q) in which P is the min-knapsack polytope and Q is the (unbounded)
polyhedron defined by the knapsack cover inequalities.
Ideally, we would like to design a communication protocol for S, as those discussed in Section 2.2,
with low communication complexity. This would imply a low-rank non-negative factorization of S.
From the factorization theorem of Section 2.1, it would follow that there exists a small-size extended
formulation yielding a polyhedron R containing the min-knapsack polytope P and contained in the
knapsack-cover relaxation Q. Hence, we would get a small-size LP relaxation for min-knapsack that
implies the exponentially many knapsack cover inequalities, and thus have integrality gap at most 2.
However, due to the fact that the quantities involved can be exponential in n, making them too
expensive to communicate directly, we have to settle for showing the existence of a small-size extended
formulation that approximately implies the knapsack cover inequalities. Before discussing further these
complications, we give an idealized version of the protocol to help with the intuition. Assume for now
that all item sizes and the demand are polynomial in n. Thus Alice and Bob can communicate them with
O(log n) bits.
The goal of the two players is to compute the slack Sa,b = ∑i:ai =0 s0i bi − U, when Alice is given
an infeasible a ∈ {0, 1}n and Bob is given a feasible b ∈ {0, 1}n . That is, after several rounds of
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 9
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
communication, either one of them outputs some non-negative value ξ , such that the expectation of ξ
equals Sa,b .
We define for a set of items J ⊆ [n] the quantity s(J) := ∑ j∈J s j , and s0 (J) := ∑ j∈J s0j . Let A and B be
the subsets of [n] corresponding to Alice’s input a and Bob’s input b, respectively. The slack we want to
compute thus becomes s0 (B r A) −U.
At the beginning, Alice computes the residual demand U and sends it to Bob. Now observe that if
there is some i∗ ∈ B r A, such that si∗ ⩾ U, then we have s0i∗ = U, and we can easily write the slack as
s0 (B r (A ∪ {i∗ })) + (s0i∗ −U) = s0 (B r (A ∪ {i∗ }))
(similarly to the uncapacitated case discussed in the introduction). Recall that we call an item i large if
si ⩾ U and small otherwise. Let Ilarge be the set of large items and Ismall be the set of small items.
The rest of the protocol is divided into two cases as follows, depending on whether Alice and Bob
can easily find a large item i∗ ∈ B r A. To this end, Alice sends s(Ilarge ∩ A) to Bob. Note that now Bob
can compute s(Ismall ∩ A) = D −U − s(Ilarge ∩ A). Bob computes the contribution of large items in B, that
is, s(Ilarge ∩ B).
If s(Ilarge ∩ B) > s(Ilarge ∩ A), then we are guaranteed that there is some i∗ ∈ Ilarge ∩ (B r A). Moreover,
defining the threshold function
(
1 if ∑i∈Ilarge si xi ⩾ s(Ilarge ∩ B),
g(x) := (3.1)
0 otherwise,
we have g(a) = 0 and g(b) = 1. Hence, Alice and Bob can find such an item with O(log2 n) bits of
communication, see Section 2.3. With that, it is not hard to compute s0 (B r (A ∪ {i∗ })) with O(log n) bits
of communication: Alice samples a uniformly random item i and sends the index to Bob, Bob replies with
bi , Alice outputs s0i · n if bi = 1, i 6= i∗ and i ∈
/ A, and outputs 0 otherwise. All her outputs are non-negative
and their expectation is exactly the slack.
In the other case, s(Ilarge ∩ B) ⩽ s(Ilarge ∩ A). Unlike in the previous case, we present a simple protocol
that does not use monotone circuits. Note that
s(B) = s(Ilarge ∩ B) + s(Ismall ∩ B) ⩾ D = s(Ilarge ∩ A) + s(Ismall ∩ A) +U ,
thus
s(Ismall ∩ B) − s(Ismall ∩ A) −U ⩾ s(Ilarge ∩ A) − s(Ilarge ∩ B) ⩾ 0 .
We now write the slack as
s0 (B r A) −U = s0 (Ilarge ∩ (B r A)) + s(Ismall ∩ (B r A)) −U
= s0 (Ilarge ∩ (B r A)) + s(Ismall ∩ B) − s(Ismall ∩ (A ∩ B)) −U
= s0 (Ilarge ∩ (B r A)) + s(Ismall ∩ B) − s(Ismall ∩ A) + s(Ismall ∩ (A r B)) −U
= s0 (Ilarge ∩ (B r A)) + s(Ismall ∩ (A r B)) + (s(Ismall ∩ B) − s(Ismall ∩ A) −U) .
Alice and Bob can compute the first and the second term in expectation using a protocol similar to that
in the previous case. The last term can be computed by Bob with all the information he has at this
stage. To conclude, in both cases, Alice and Bob can compute the exact slack Sa,b with O(log2 n) bits of
communication.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 10
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
3.2 The protocol
The actual slack matrix Sε we work with is defined as
2
ε
Sa,b := ∑ s0i bi − U, (3.2)
i:ai =0 2+ε
where ε > 0 is any small constant, a ∈ f −1 (0) and b ∈ f −1 (1). Sε is the slack matrix of the polyhedral pair
(P, Qε ) where P is the min-knapsack polytope and Qε is the polyhedron defined by a slight weakening of
the knapsack cover inequalities obtained by replacing the right-hand side of (1.1) by (2/(2 + ε)) ·U < U.
For every x ∈ Rn⩾0 that satisfies all weakened knapsack cover inequalities, we have that ((2 + ε)/2)x
satisfies all original knapsack cover inequalities, and thus, by virtue of [15], (2 + ε)x dominates a convex
combination of feasible solutions. Therefore the integrality gap of the resulting LP relaxation (obtained
from a non-negative factorization of Sε ) is at most 2 + ε.
In order to refer to the “derived” weighted threshold functions g as in (3.1), we need a last bit of
terminology. We say that g : {0, 1}n → {0, 1} is a truncation of f if there exist U, T ∈ Z>0 with T ⩽ D
such that g(x) = 1 iff ∑ni=1 wi xi ⩾ T , where wi = si if si ⩾ U and wi = 0 otherwise. We are now ready to
state our main technical lemma.
Lemma 3.1. For all constants ε ∈ (0, 1), item sizes si ∈ Z>0 (i ∈ [n]), all smaller than 2dn log ne , and
demand D ∈ Z>0 with max{si | i ∈ [n]} ⩽ D ⩽ ∑ni=1 si , such that all truncations of the corresponding
weighted threshold function admit depth-t monotone circuits of fan-in 2, there is a O(log(1/ε) + log n +t)-
complexity randomized communication protocol with non-negative outputs that computes the slack matrix
Sε in expectation. Since we may always take t = O(log2 n), this gives a O(log(1/ε) + log2 n)-complexity
protocol.
Before giving the proof, let us remark that the first part of Theorem 1.1 follows directly from this
lemma. Indeed, the extra assumptions in the lemma are without loss of generality: the fact that we may
assume without loss of generality that the item sizes si are positive integers that can be written down with
at most dn log ne bits, is due to a classic result from [36] (cf. [35]); and the fact that we may also assume
that the demand D is a positive integer with max{si | i ∈ [n]} ⩽ D ⩽ ∑ni=1 si should be clear.
Moreover, Lemma 3.1 implies that we can obtain a relaxation of polynomial size if all truncations
of the weighted threshold function have monotone circuits of logarithmic depth. In particular, this is
the case if all item sizes are polynomial in n. In that case the threshold function (and its truncations)
can simply be written as the majority function on O(∑i si ) input bits by using the unary representation
of numbers5 and, as such functions have monotone circuits of fan-in 2 of logarithmic depth [1], i. e.,
depth O(log (∑i si )). Thus, using majority functions instead of threshold functions in our communication
protocol, we get that for all ε ∈ (0, 1), c > 0, item sizes s1 , . . . , sn ∈ {0, 1, . . . , nc } and demand D ∈ N,
there exists a size-(1/ε)O(1) nO(c) extended formulation defining an LP relaxation of min-knapsack with
integrality gap at most 2 + ε. However, it is important to note here that when c is a constant (and hence
5 To be precise, the majority circuit takes
∑ni=1 si + A bits as input. The first ∑i si bits are the representation of the numbers
s1 , . . . , sn in unary; the inputs that interest us are those where, for every i ∈ [n], the si bits corresponding to si are all set to 0 or 1.
Finally, the additional A bits are set to constants 0 or 1 so as to make sure that the majority outcome corresponds to the given
threshold. Note that A is at most ∑i si and thus the majority function is on at most O(∑i si ) bits.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 11
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
the sizes s1 , . . . , sn and the demand D are polynomial in n), we can write down an exact polynomial-size
LP formulation of the min-knapsack problem.6
We now proceed by proving our main technical result, i. e., Lemma 3.1.
Proof of Lemma 3.1. Let α = α(ε) := 2/(2 + ε) and δ > 0 be such that (1 − 2δ )/(1 + δ ) = α. Thus
δ = ε/(6 + 2ε) = Θ(ε). As above, we denote by a ∈ f −1 (0) the input of Alice and by b ∈ f −1 (1) that
of Bob, and let A and B denote the corresponding subsets of [n].
First, Alice tells Bob the identity of the set of large items Ilarge = {i ∈ [n] | si ⩾ U} and its complement,
the set of small items Ismall . This costs O(log n) bits of communication. For instance, Alice can simply
send the index of a smallest large item to Bob, or inform Bob that Ilarge is empty. Recall that
U = D − s(A) = D − s(Ilarge ∩ A) − s(Ismall ∩ A) .
Then, Alice sends Bob the unique nonnegative integer k such that (1 + δ )k ⩽ U < (1 + δ )k+1 . This
2 2
sets the scale at which the protocol is operating. Since U ⩽ n · 2dn log ne ⩽ 2n , we have (1 + δ )k ⩽ 2n . This
implies that k = O((1/ε)n2 ), thus k can be sent to Bob with log(1/ε) + 2 log n + O(1) = O(log(1/ε) +
log n) bits. Let Ue := (1 + δ )k .
To efficiently communicate an approximate value of s(Ilarge ∩ A), Alice sends the unique nonnegative
integer ` such that
(1 + `δ )Ue < D − s(Ilarge ∩ A) ⩽ (1 + `δ )U e + δ U.
e
Since small items have size at most U and we have at most n of them, we have s(Ismall ∩ A) ⩽ Un. Hence,
D − s(Ilarge ∩ A) = U + s(Ismall ∩ A) ⩽ (n + 1)U ⩽ (n + 1)(1 + δ )U
e.
Since (1 + `δ )Ue < (n + 1)(1 + δ )U, e we have ` = O((1/ε)n). This means that Alice can communicate
` to Bob with only O(log(1/ε) + log n) bits. Let ∆˜ = ∆(δ ˜ ) := (1 + `δ )U.
e This is Bob’s strict under-
approximation of D − s(Ilarge ∩ A), so that D − ∆˜ is a strict over-approximation of s(Ilarge ∩ A).
Bob checks if s(Ilarge ∩ B) ⩾ D − ∆. ˜ If this is the case, then the weighted threshold function g such
˜
that g(x) = 1 iff ∑i∈Ilarge si xi ⩾ D − ∆ separates a from b in the sense that g(a) = 0 and g(b) = 1. Since g
is a truncation of f , Alice and Bob can exchange t bits to find an index i∗ ∈ Ilarge such that ai∗ = 0 and
bi∗ = 1.
We can rewrite the slack Sa,b ε = s0 (B r A) − αU as
s0 (B r (A ∪ {i∗ })) + s0i∗ − αU = s0 (B r (A ∪ {i∗ })) + (U − αU) = ∑ s0i bi + (U − αU) . (3.3)
i:ai =0, i6=i∗
With the knowledge of i∗ , Alice and Bob can compute the slack as follows:
6 This can be done by casting the folklore Dynamic Programming algorithm for the min-knapsack problem, as a minimum
s-t flow problem on a weighted graph G with polynomially many vertices, and arguing that the well-known exact LP relaxation
of the latter is also an exact LP relaxation of the former. The reader familiar with the dynamic programming algorithm should
notice that the edges G would only depend on the sizes of the items, whereas the weights on these edges would only depend on
the costs of the items. Hence in the resulting LP formulation, the constraints depend only on the sizes, and the costs only appear
in the objective function.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 12
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
1. Alice samples a uniformly random number i ∈ [n]. If i ∈
/ A, continue to the next step, otherwise
Alice outputs 0 and terminates the communication.
2. If i = i∗ , Alice outputs n · (U − αU) and terminates the communication, otherwise continue.
3. Alice sends i to Bob using dlog ne bits of communication, and Bob sends bi back to Alice.
4. Alice outputs n · s0i bi .
The above communication costs O(log n) bits, all outputs are non-negative and can be computed with the
information available to each player, and by linearity of expectation, the expected output is exactly the
slack (3.3). Together with the O(log(1/ε) + log n + t) bits communicated previously, we conclude that in
this case there is a protocol that computes the slack in expectation with O(log(1/ε) + log n + t) bits of
communication.
˜ Because b ∈ {0, 1}n is feasible, we get
In the other case, we have s(Ilarge ∩ B) < D − ∆.
s(B) ⩾ D ⇐⇒ s(Ilarge ∩ B) +s(Ismall ∩ B) ⩾ D ,
| {z }
<D−∆˜
therefore we can bound s(Ismall ∩ B) as
s(Ismall ∩ B) > ∆˜ ⩾ D − s(Ilarge ∩ A) − δ U
e = s(Ismall ∩ A) +U − δ U
e ⩾ σe + (1 − δ )U
e, (3.4)
where σe is the unique integer multiple of δ U
e such that
σe ⩽ s(Ismall ∩ A) < σe + δ U
e. (3.5)
Since σe ⩽ s(Ismall ∩A) ⩽ Un ⩽ (1+δ )Un,
e Alice can communicate σe to Bob with O(log(1/ε)+log n)
bits.
This implies
s(Ismall ∩ (B r A)) = s(Ismall ∩ B) − s(Ismall ∩ (A ∩ B)) > σ
e + (1 − δ )U
e − s(Ismall ∩ (A ∩ B)) .
e we have (1 + δ )U
Recall that by definition of U, e > U, therefore
(1 − 2δ )U
e − αU > (1 − 2δ )U
e − α(1 + δ )U
e = 0. (3.6)
We now rewrite the slack as
s0 (B r A) − αU = s0 (Ilarge ∩ (B r A)) + s(Ismall ∩ B) − σe − (1 − δ )U
e + s(Ismall ∩ (A r B))
| {z } | {z } | {z }
= ∑i∈Ilarge rA s0i bi non-negative by (3.4) ∑i∈Ismall ∩A si (1−bi )
e − s(Ismall ∩ A) + (1 − δ )U
+σ e − αU .
| {z }
non-negative by (3.5) and (3.6)
The slack can now be readily computed using the following protocol.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 13
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
1. Alice samples a uniformly random number i ∈ [n + 2]. If i = n + 2, Alice outputs the normalized
value of the last term, i. e., (n + 2) · (σ
e − s(Ismall ∩ A) + (1 − δ )U
e − αU), and terminates the
communication. Otherwise, she sends i to Bob using O(log n) bits.
2. If i = n + 1, Bob outputs (n + 2) · (s(Ismall ∩ B) − σ
e − (1 − δ )U),
e and ends the communication.
Otherwise, he replies to Alice with bi .
3. If i ∈ Ilarge r A, Alice outputs (n + 2) · s0i bi ; if i ∈ Ismall ∩ A, she outputs (n + 2) · si (1 − bi ); otherwise
she outputs 0.
We can verify that the outputs of both players can be computed with information available to them,
and that the outputs are non-negative due to Equation (3.4), (3.5) and (3.6), and the definition of the
variables.
4 Flow-cover inequalities
Adapting the combinatorial insight behind the knapsack cover inequalities to other settings has led to
numerous strong relaxations. In particular, the flow cover inequalities have been used to strengthen LPs
for many problems such as the Fixed Charge Network Flow problem [15] and the Single-Demand Facility
Location problem [14]. In this section, we describe the application of flow cover inequalities to the
Single-Demand Facility Location problem as used in [14], and then show that we can adapt our approach
from the previous section to give an O(log2 n)-bit two-party communication protocol that computes a
weakened version of these inequalities.
In the Single-Demand Facility Location problem, we are given a set F of n facilities, such that each
facility i ∈ F has a capacity si , an opening cost fi , and a per-unit cost ci to serve the demand. The goal is
to serve the demand D by opening a subset S ⊆ F of facilities such that the combined cost of opening
these facilities and serving the demand is minimized. The authors of [14] cast this problem as an Integer
Program, and showed that its natural LP relaxation has an unbounded integrality gap. To reduce this gap,
they strengthened the relaxation by adding the so-called flow cover inequalities that we define shortly.
(See Section 3 in [14] for a more elaborate discussion.)
A feasible solution (x, y) with y ∈ {0, 1}n and x ∈ [0, 1]n for the Single-Demand Facility Location LP
can be thought of as follows: for each i ∈ F, yi ∈ {0, 1} indicates if the i-th facility is open, and xi ∈ [0, 1]
indicates the fraction of the demand D being served by the i-th facility. A feasible solution (x, y) must
then satisfy that
1. the demand is met, i. e., ∑i xi = 1;
2. no facility is supplying more than its capacity, i. e., 0 ⩽ xi D ⩽ yi si for all i ∈ F.
For a subset J ⊆ F of facilities and a feasible solution (x, y), we denote by B = {i ∈ F : yi = 1} ⊆ [F] the
set of open facilities according to y, and we define the quantity x(J) to be the overall demand served by
the facilities in J, i. e., x(J) = ∑i∈J xi D.7 We also define the quantities s(·) and s0 (·) as in Section 3.1.
7 Note that since we are assuming that (x, y) is feasible, we get that x(J) = x(J ∩ B).
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 14
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
Carnes and Shmoys [14] showed that adding the flow cover inequalities (FCI) reduces the integrality
gap of the natural LP relaxation down to 2. These inequalities are defined as follows: for any infeasible set
A ⊆ F (i. e., A ⊆ F such that s(A) < D), and for all partitions of F \ A = F1 t F2 , the following inequality
holds for all feasible solutions (x, y):
s0 (F1 ∩ B) + x(F2 ∩ B) ⩾ U , (FCI)
where U = D − s(A) is the residual demand and s0i = min{si ,U}. For brevity, we refer to an infeasible set
A along with some partition F1 t F2 = F \ A as an infeasible tuple (A, F1 , F2 ). Note that for F2 = 0,
/ the
flow-cover inequalities are the same as the knapsack cover inequalities. The main result of this section is
formally stated in the following theorem:
Theorem 4.1. For all ε ∈ (0, 1), capacities s1 , . . . , sn ∈ R+ and demand D ∈ R+ , there exists a size-
(1/ε)O(1) nO(log n) extended formulation defining an LP relaxation of the Single-Demand Facility Location
problem with integrality gap at most 2 + ε.
As in the knapsack cover inequalities, the goal is to compute the slack of a relaxed version of (FCI)
in expectation for any feasible solution (x, y) and any infeasible tuple (A, F1 , F2 ). Namely, let ε ∈ (0, 1)
and α = 2/(2 + ε). Our goal is to design an O(log2 n + log(1/ε))-complexity two-party communication
protocol with private randomness and nonnegative outputs whose expected output equals s0 (F1 ∩ B) +
x(F2 ∩ B) − αU. That is, we want to compute the slack with respect to a given (weakened) flow-cover
inequality s0 (F1 ∩ B) + x(F2 ∩ B) ⩾ αU, where the RHS of (FCI) is replaced by αU. This implies the
existence of an LP of size (1/ε)O(1) nO(log n) with an integrality at most 2 + ε for the Single-Demand
Facility Location problem.
In Section 4.1, we set up the notation and define a class of feasible solutions with a certain special
structure which we refer to as canonical feasible solutions. We design the promised communication
protocol restricted to canonical solutions in Section 4.2, and extend it to arbitrary feasible solutions in
Section 4.3.
4.1 Preliminaries
Let (x, y) be a feasible solution for the flow-cover problem with demand D, and let B = {i ∈ F : yi = 1}
denote the support of y. In this terminology, B only indicates which facilities are open, but it does not
capture the relative demand being served through each of them. However this distinction will be essential
for designing the protocol, hence we partition B into three disjoint sets B = Fe1 t Fe2 t Fe3 as follows:
Fe1 = {i ∈ B : xi D = si yi = si } , Fe2 = {i ∈ B : 0 < xi D < si } , Fe3 = {i ∈ B : xi D = 0} .
We first focus on feasible solutions (x, y) that exhibit a certain structure, and then generalize to arbitrary
solutions. Specifically, we restrict our attention here and in Section 4.2 to canonical feasible solutions
defined as follows.
Definition 4.2. A feasible solution (x, y) with associated sets Fe1 , Fe2 , Fe3 is canonical if Fe2 contains at most
one facility, i. e., |Fe2 | ⩽ 1. In other words, in a canonical feasible solution, there is at most one facility j
that supplies a non-zero demand x j D > 0 which is not equal to its full capacity s j .
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 15
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
Recall that we are interested in computing
s0 (F1 ∩ B) + x(F2 ∩ B) − αU (4.1)
in expectation, which can be expanded as follows:
s0 (F1 ∩ Fe1 ) + s0 (F1 ∩ Fe2 ) + s0 (F1 ∩ Fe3 ) + x(F2 ∩ Fe1 ) + x(F2 ∩ Fe2 ) + x(F2 ∩ Fe3 ) − αU . (4.2)
We get from the definition of the set Fe3 that the second to last term in the above equation is 0 when
restricted to canonical feasible solutions. In fact, one can completely get rid of the overall contribution
of Fe3 in the above equation, since intuitively, closing down the facilities in Fe3 should not alter the
feasibility of the solution, and hence Equation (4.2) should still be positive even without accounting
for the contribution of s0 (F1 ∩ Fe3 ). In the communication protocol setting, this intuition translates to
designing a protocol that only deals with canonical feasible solutions restricted to Fe3 = 0. /
To see that this is without loss of generality, consider a canonical feasible solution (x, y) such that
Fe3 is not empty, and let (x, ȳ) be the projection of (x, y) on Fe1 ∪ Fe2 —that is, for all i ∈ B \ Fe3 , set ȳi = yi ,
and for all i ∈ Fe3 , set ȳi = 0. It follows that (x, ȳ) is also a canonical feasible solution, as the items whose
support is Fe3 do not contribute to the feasibility of the solution, and the cardinality of Fe2 does not change.
Thus, for any infeasible tuple (A, F1 , F2 ), Equation (4.2) applied to (x, ȳ) can be written as
s0 (F1 ∩ Fe1 ) + s0 (F1 ∩ Fe2 ) + x(F2 ∩ Fe1 ) + x(F2 ∩ Fe2 ) − αU , (4.3)
which is also non-negative, as it is the slack of (x, ȳ) and (A, F1 , F2 ). Therefore, for any feasible solution
(x, y), the slack as given by Equation (4.2) can be viewed as the summation of Equation (4.3) and the
non-negative term s0 (F1 ∩ Fe3 ). The latter is easy to compute with a small communication protocol,8 thus if
Alice and Bob can devise a communication protocol Π that computes (4.3) in expectation, they can then
easily compute (4.2) in expectation. For example, Alice can generate a uniformly random bit b ∈ {0, 1},
and
• if b = 0, then Alice and Bob run the protocol that computes s0 (F1 ∩ Fe3 ), and return twice its output;
• if b = 1, then Alice and Bob run the protocol Π that computes (4.3), and return twice its output.
Moreover, since |Fe2 | ⩽ 1, and using the fact that xi D = si for i ∈ Fe1 , we can further simplify Equa-
tion (4.3) as follows:
s0 (F1 ∩ Fe1 ) + s(F2 ∩ Fe1 ) + γ(x, y, A, F1 , F2 ) − αU , (4.4)
where the function γ := γ(x, y, A, F1 , F2 ) is defined as
0 if Fe2 = { j} ⊆ F1 ,
s j
γ = x jD if Fe2 = { j} ⊆ F2 , (4.5)
0 if Fe2 = { j} ⊆ A, or Fe2 = 0/ .
For simplicity of notation, we drop the parameters from γ(x, y, A, F1 , F2 ) when they are clear from the
context.
8 To compute s0 (F ∩ F e3 ), Bob samples an index i ∈ [n]. If i ∈ / Fe3 , he outputs 0 and terminates the protocol, otherwise he
1
sends i to Alice. If i ∈ F1 , Alice outputs n · s0 (i), otherwise, she outputs 0.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 16
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
4.2 Randomized protocol for canonical feasible solutions
In what follows, we define a randomized communication protocol where Alice gets an infeasible tuple
(A, F1 , F2 ), and Bob gets a canonical feasible solution (x, y) with Fe3 = 0, / and the goal is to compute the
value of (4.4) in expectation.
For a fixed ε > 0, we define α := α(ε) = 2/(2 + ε), δ := δ (ε) = ε/(6 + 2ε) as in the min-knapsack
case. Like the protocol for the knapsack cover inequalities, Alice sends Bob O(log n) bits at the beginning
so that Bob knows Ilarge , Ismall , U, e Recall that Ilarge is the set of large items (i. e., i ∈ F such that
e σe and ∆.
e is an under-approximation of the residual demand U, D − ∆
si ⩾ U), Ismall is the set of small items, U e is an
over-approximation of s(Ilarge ∩ A) and σ is an under-approximation of s(Ismall ∩ A). Moreover, knowing
e
his input (x, y), Bob can construct the sets Fe1 and Fe2 . Thus, by exchanging an additional O(log n) bits,
Alice and Bob can both figure out which condition is satisfied for Equation (4.5).
To compute the value of (4.4) in expectation, we distinguish between the following cases:
Case 1: Either Fe2 = 0,/ or Fe2 = { j} and j ∈ A ∪ F1 . In this case, we have that the value γ is either 0 or
0
s j y j . Bob now checks if
s(Ilarge ∩ (Fe1 ∪ Fe2 )) ⩾ D − ∆
e. (4.6)
Equation (4.6) holds: In the same way as in the min-knapsack protocol, Alice and Bob exchange
O(log2 n) bits to identify an index i∗ ∈ Ilarge such that i∗ ∈ ((Fe1 ∪ Fe2 ) \ A). More precisely, this
index i∗ belongs to one of the following three sets: either i∗ ∈ F1 ∩ Fe1 , or i∗ ∈ F2 ∩ Fe1 , or i∗ = j
and Fe2 = { j}. Alice and Bob can thus exchange O(1) more bits to figure out the condition that i∗
satisfies. In what follows, we design an O(log n)-communication protocol to handle each of these
cases.
If i∗ ∈ F2 ∩ Fe1 , then Equation (4.4) can be rewritten as
s0 (F1 ∩ Fe1 ) + s((F2 ∩ Fe1 ) \ {i∗ }) + γ + (si∗ − αU) . (4.7)
One can see that each of the above four terms is non-negative, and similar to the min-knapsack
protocol, Alice and Bob can exchange O(log n) bits and compute the value of (4.7) as follows:
1. Bob sends Alice the index j using dlog(n)e bits if and only if Fe2 = { j}, and he sends n + 1 if
Fe2 = 0.
/
2. Alice samples a uniformly random index i ∈ [n + 1]. If i = n + 1, Alice uses the knowledge
of Fe2 (and thus γ) to compute the normalized value of the last terms, that is, she outputs
(n + 1) · (γ + si∗ − αU), and terminates the communication. Otherwise, she sends i to Bob
using dlog(n)e bits.
3. If i ∈ Fe1 , Bob sends 1 to Alice; otherwise, Bob outputs 0 and terminates the communication.
4. If i ∈ F1 , Alice outputs (n + 1) · s0i ; if i ∈ F2 \ {i∗ }, she outputs (n + 1) · si ; otherwise she
outputs 0.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 17
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
The above communication costs O(log n) bits, all outputs are non-negative and can be computed
with the information available to each player, and by linearity of expectation, the expected output
is exactly the slack (4.4) when i∗ ∈ F2 ∩ Fe1 .
The case where i∗ ∈ F1 ∩ Fe1 is handled similarly.
In the remaining case, we have Fe2 = { j} and i∗ = j ∈ F1 ∩ Ilarge , and hence γ = s0j > αU. This can
be handled by changing the second step of the protocol described earlier in such a way that Alice
outputs (n + 1) · (s0j − αU) if i = n + 1.
Equation (4.6) does not hold: Recall that since (x, y) is a feasible solution (and Fe3 = 0),
/ we have
D ≤ x(Fe1 ) + x(Fe2 )
= x(Ismall ∩ Fe1 ) + x(Ismall ∩ Fe2 ) + x(Ilarge ∩ Fe1 ) + x(Ilarge ∩ Fe2 )
≤ x(Ismall ∩ Fe1 ) + x(Ismall ∩ Fe2 ) + s(Ilarge ∩ Fe1 ) + s(Ilarge ∩ Fe2 )
= x(Ismall ∩ Fe1 ) + x(Ismall ∩ Fe2 ) + s(Ilarge ∩ (Fe1 ∪ Fe2 )) .
By the assumption that Equation (4.6) does not hold, together with the argument in Equation (3.4),
we conclude that
x(Ismall ∩ Fe1 ) + x(Ismall ∩ Fe2 ) > ∆ e ⩾ σe + (1 − δ )U e. (4.8)
Note that since |Fe2 | ⩽ 1, we get that
0
if Fe2 = 0/ ,
x(Ismall ∩ Fe2 ) = 0 if Fe2 = { j} ⊆ Ilarge ,
x jD if Fe2 = { j} ⊆ Ismall .
We also have that x(Ismall ∩ Fe1 ) = s(Ismall ∩ Fe1 ) by the definition of Fe1 . Together this gives that the
summation s(Ismall ∩ Fe1 ) + x(Ismall ∩ Fe2 ) is lower bounded by σ e + (1 − δ )U.e We rewrite (4.4) as
s0 (F1 ∩ Fe1 ) + s(F2 ∩ Fe1 ) + γ − αU (4.9)
= s0 (Ilarge ∩ F1 ∩ Fe1 ) + s(Ilarge ∩ F2 ∩ Fe1 ) + s(Ismall ∩ (Fe1 \ A)) + γ − αU
= s0 (Ilarge ∩ F1 ∩ Fe1 ) + s(Ilarge ∩ F2 ∩ Fe1 ) + s(Ismall ∩ (A \ B)) + s(Ismall ∩ A ∩ Fe2 )
+ s(Ismall ∩ Fe1 ) − s(Ismall ∩ A) + γ − αU .
The non-negativity of the first three terms is straightforward, and Alice and Bob can compute them
by exchanging O(log n) bits.9 By adding and subtracting (σ e + (1 − δ )U
e − x(Ismall ∩ Fe2 )) to the
remaining terms in (4.9), we can rearrange the terms and rewrite the rest as the sum of the following
three non-negative terms that we can easily compute:
s(Ismall ∩ Fe1 ) − σe − (1 − δ )U
e + x(Ismall ∩ Fe2 ) + σe + (1 − δ )U
e − αU − s(Ismall ∩ A)
+ s(Ismall ∩ A ∩ Fe2 ) + γ − x(Ismall ∩ Fe2 ) . (4.10)
9 For instance, to compute s0 (I
large ∩ F1 ∩ F1 ), Alice samples uniformly i ∈ [n] and sends it to Bob, Bob responds with b = 1
e
if i ∈ Fe1 and b = 0 otherwise. Alice then outputs n · s0i if i ∈ Ilarge ∩ F1 and b = 1, and 0 otherwise. The protocols for the second
and the third terms are very similar.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 18
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
The non-negativity of the first part follows from (4.8), and Bob has all the information to compute
it on his own. The non-negativity of the second part follows from our definition of σe and U, e and
their relation to δ and α. Moreover, Alice has all the information to compute this part.
To see that the third part (i. e., s(Ismall ∩ A ∩ Fe2 ) + γ − x(Ismall ∩ Fe2 )) is also non-negative and can
easily be computed by one of the players, note the following.
1. If x(Ismall ∩ Fe2 ) = 0, then clearly it is non-negative. In this case, Bob communicates the set Fe2
to Alice using O(log n) bits so that she knows whether Fe2 = 0, / or the item j if Fe2 = { j} and
j ∈ Ilarge . Once Fe2 is known to Alice, she can compute both s(Ismall ∩ A ∩ Fe2 ) and γ (recall
that γ would be either 0 or s0j y j = U).
2. If x(Ismall ∩ Fe2 ) = x j D 6= 0, then we have that Fe2 = { j} and j ∈ Ismall . From our assumption
of Case 1, we also have that j ∈ A ∪ F1 . Since A and F1 are two disjoint sets, we get that:
(a) If j ∈ A, then
s(Ismall ∩ A ∩ Fe2 ) + γ −x j D = s j y j − x j D ⩾ 0 .
| {z } |{z}
s jy j 0
(b) If j ∈ F1 , then
s(Ismall ∩ A ∩ Fe2 ) + γ −x j D = s j y j − x j D ⩾ 0 .
| {z } |{z}
0 s jy j
Thus it is also non-negative, and Bob can compute it on his own in this case.
/ or Fe2 = { j} where
This concludes the communication protocol in the case where either Fe2 = 0,
j ∈ A ∪ F1 .
Case 2: Fe2 = { j} and j ∈ F2 . In this case γ = x j D. This case is quite similar to Case 1, with the difference
being that Bob checks at the beginning if
s(Ilarge ∩ Fe1 ) ⩾ D − ∆
e,
i. e., without including Fe2 compared to (4.6).
If the condition was indeed satisfied, then the same reasoning as the first part of Case 1 resolves
this case. Otherwise, we get
s(Ismall ∩ Fe1 ) + x j D > σe + (1 − δ )U
e, (4.11)
and using Equation (4.9) from the second part of Case 1 yields that that first four terms in this case
are non-negative and easy to compute. Similarly, adding and subtracting (σe + (1 − δ )U)e to the last
four terms of (4.9), and rearranging the terms we get
s(Ismall ∩ Fe1 ) − σ
e − (1 − δ )U
e + x jD + σe + (1 − δ )U
e − αU − s(Ismall ∩ A) .
The first part of the summation is non-negative by Equation (4.11) and can be computed by Bob.
The second part is the same as the second part in Equation (4.10). It is non-negative by definition
and can be computed by Alice. This completes the proof.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 19
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
This concludes the promised communication protocol in the case where Alice is given an infeasible tuple
(A, F1 , F2 ), and Bob is given a canonical feasible solution with Fe3 = 0.
/ As argued in Section 4.1, this
generalizes to any canonical feasible solution without any restriction on Fe3 .
4.3 Randomized protocol for arbitrary feasible solutions
We now extend the communication protocol of canonical feasible solutions to arbitrary feasible solutions.
To that end, we denote by R = {(x1 , y1 ), (x2 , y2 ), . . . , (xr , yr )} the set of all canonical feasible solutions.
In this non-restricted setting, Alice still gets an infeasible tuple (A, F1 , F2 ), but Bob gets a feasible
solution (x, y) that is not necessarily canonical, and the goal remains to compute the slack of the corre-
sponding flow-cover inequality (i. e., Equation (4.1)) in expectation. We show that the communication
protocol that we developed in the previous section can be used as a black-box to handle this general case,
by noting that any feasible solution (x, y) can be written as a convex combination of canonical feasible
solutions (x1 , y1 ), (x2 , y2 ), . . . , (xr , yr ). This is formalized in Lemma 4.3.
Lemma 4.3. Let R = {(x1 , y1 ), (x2 , y2 ), . . . , (xr , yr )} be the set of all the canonical feasible solutions for
the flow cover problem, then any feasible solution (x, y) can be written as
r
(x, y) = ∑ λk (xk , yk ) , (4.12)
k=1
such that λk ⩾ 0 for all 1 ⩽ k ⩽ r, and ∑k λk = 1.
To see that this is enough, note that for any constraint the slack of (x, y), say aT (x, y) − b ≥ 0, equals
the convex combination of the slacks of the canonical feasible solutions:
r
T k k
∑ λk · a (x , y ) − b .
k=1
Thus in order to compute the slack of (4.1) in expectation, Bob samples a canonical feasible solution
(xk , yk ) ∈ R with probability λk , then together with Alice, they compute the slack of
∑ s0i yki + ∑ xik D − αU
i∈F1 i∈F2
as discussed in the previous section.
We conclude this section by proving Lemma 4.3.
Proof of Lemma 4.3. Given a feasible solution (x, y), define its support Fex,y = {i : i ∈ F, and yi = 1}, and
define the set Rx,y to be the set of all canonical feasible solutions whose support equals Fex,y , i. e.,
Rx,y = {(x0 , y) : (x0 , y) ∈ R} ⊆ R .
Without loss of generality, we assume that Fex,y = [n] to simplify the presentation.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 20
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
We now consider the following polytope P(y):
z ∈ [0, 1]n ,
such that:
P(y) = (∗) ∑ni=1 zi = 1 ,
(∗∗) 0 ⩽ zi ⩽ sDi yi for all 1 ⩽ i ⩽ n .
Note that for any feasible solution (x, y) to the flow cover problem, we have that x ∈ P(y). Moreover, we
get from Definition 4.2 that for any canonical feasible solution (x0 , y) ∈ Rx,y , all except at most one item
i ∈ [n], either has xi0 = 0 or xi0 D = si yi . Thus x0 satisfies at least n − 1 linearly independent constraints of
type (∗∗) with equality. Conversely, if a point x ∈ P(y) satisfies at least n − 1 constraints of type (∗∗)
with equality, then (x, y) ∈ Rx,y .
Recall that a point z is an extreme point solution of P(y) iff there are n linearly independent constraints
that are set to equality by z. Since constraint (∗) is an equality constraint and is linearly independent from
any set of n − 1 constraints from (∗∗), we conclude that {x0 : (x0 , y) ∈ Rx,y } is the set of all extreme points
of P(y). This implies that for any x ∈ P(y), there exists λk ⩾ 0 for each 1 ⩽ k ⩽ r such that ∑k λk = 1 and
r
x = ∑ λk xk .
k=1
Since all these points have the same y-support, it follows that
r
(x, y) = ∑ λk (xk , yk ) .
k=1
5 Constructing the extended formulation
We proved the first part of Theorem 1.1 in Section 3. Here, we prove the second part of Theorem 1.1 and
show how to construct an extended formulation in quasi-polynomial time. The construction is based for
one part on our ideas, and for the other part on recent results by Fiorini, Huyhn and Weltge [24] that were
established after this article was submitted.
Second part of Theorem 1.1. We use the same notation as in the proof of Lemma 3.1. Remember that
Ilarge ⊆ [n] is the set of large items, Ismall = [n] \ Ilarge is the set of small items, and ∆˜ is an approximation
of D − s(Ilarge ∩ A) with ∆˜ < D − s(Ilarge ∩ A). For every possible Ilarge and ∆, ˜ let f n
Ilarge ,∆˜ : {0, 1} → {0, 1}
be the weighted threshold function defined by
fIlarge ,∆˜ (x) = 1 ⇐⇒ ∑ si xi ⩾ D − ∆˜ .
i∈Ilarge
By Theorem 2.5, there exists an O(log2 n)-depth monotone circuit with fan-in 2 that computes fIlarge ,∆˜ .
2
Moreover, this circuit can be constructed in time 2O(log n) = nO(log n) . In order to use the results of [24],
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 21
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
we convert the circuit computing fIlarge ,∆˜ into a size-nO(log n) monotone Boolean formula φIlarge ,∆˜ . This can
also be done in time nO(log n) . Thus φIlarge ,∆˜ is a formula in the variables xi (i ∈ [n]) and
φIlarge ,∆˜ (x) = 1 ⇐⇒ fIlarge ,∆˜ (x) = 1
for all x ∈ {0, 1}n .
Now consider the following expression:
!!
^
ψ := φIlarge ,∆˜ ∨ ∑ si xi ⩾ ∆˜ .
Ilarge ,∆˜ i∈Ismall
We regard ψ as a formula in which each atom is either a variable xi (i ∈ [n]) or some linear inequality,
and each connector is either ∧ (AND) or ∨ (OR). We can represent ψ as a tree each of whose leaves
is labeled either by a variable xi for some i ∈ [n] (variable-leaf ) or by an inequality ∑i∈Ismall si xi ⩾ ∆˜ for
some Ilarge and ∆˜ (inequality-leaf ), and each of whose inner nodes is either an AND node or an OR node.
Let Q ⊆ [0, 1]n be any polyhedral relaxation of the set of feasible solutions
( )
n
S := x ∈ {0, 1}n : ∑ si xi ⩾ D .
i=1
Here we take simply Q := [0, 1]n . Following [24], we recursively define a new relaxation ψ(Q) from ψ.
Consider the tree of ψ. We define a polytope for each node of the tree, in a bottom-to-top fashion.
First, consider a leaf of the tree. If the leaf is a variable-leaf labeled by xi , we define the corresponding
polytope to be Q ∩ {x : xi = 1}. Otherwise, the leaf is an inequality-leaf labeled by the inequality
∑i∈Ismall si xi ⩾ ∆˜ for some choice of Ilarge and ∆.
˜ In this case we associate the polytope
( )
Q ∩ x : ∑ si xi ⩾ ∆˜
i∈Ismall
to the leaf. Next, consider an inner node of the formula tree. For this inner node, we define a polytope
that is either the intersection of the polytopes for its children, in case the inner node is an AND node, or
the convex hull of the union of the polytopes for its children, in case the inner node is an OR node. We
denote by ψ(Q) the polytope for the root node of the tree.
First, we claim that ψ(Q) is still a relaxation of S. Indeed, pick an arbitrary Ilarge and ∆, ˜ and let x ∈ S
˜
be any feasible solution. If x satisfies ∑i∈Ilarge si xi ⩾ D − ∆, one can easily check that it belongs to the
polytope for the root of the subtree that computes φIlarge ,∆˜ , see [24] for details. It is convenient to denote
˜ In this case, it is in
this polytope by φIlarge ,∆˜ (Q). Otherwise, x satisfies ∑i∈Ismall si xi ⩾ ∆.
( )
Q∩ x : ∑ si xi ⩾ ∆˜ .
i∈Ismall
It follows that every x ∈ S is in ψ(Q).
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 22
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
Second, assuming that Q has a size-k extended formulation, ψ(Q) has an extended formulation
whose size is at most (k + 1) times the number of leaves in the tree of ψ. This follows from [24]. That
is, ψ(Q) has an extended formulation of size at most (k + 1)n(1/ε)O(1) nO(1) nO(log n) = (k + 1)nO(log n) .
(Remember that there are at most n choices for Ilarge since we can assume the items to be sorted, and
at most (1/ε)O(1) nO(1) = nO(log n) choices for ∆.) ˜ For Q = [0, 1]n we have k = 2n, thus ψ([0, 1]n ) has a
quasi-polynomial-size extended formulation. Moreover, the extended formulation can be constructed in
quasi-polynomial time since all the φIlarge ,∆˜ ’s can be constructed in that time. Lastly, ψ(Q) is built from
the polytopes for the leaves of the tree of ψ by taking intersections and convex hulls of unions, for which
we can construct extended formulations efficiently, see for instance [21].
Third, we claim that the integrality gap of ψ([0, 1]n ) is at most (2 + ε). This is due to the fact that for
all a ∈ {0, 1}n the weakened knapsack cover (KC) inequality
∑ s0i xi ⩾ αU (5.1)
i:ai =0
is valid for ψ([0, 1]n ), where as before α = 2/(2 + ε) is a number slightly below 1. As in the proof of
Lemma 3.1, to every such inequality corresponds a unique set Ilarge and number ∆.˜ Below, we verify that
(5.1) is valid for both polytopes
( )
φ n n
˜ ([0, 1] ) and [0, 1] ∩ x : ∑ si xi ⩾ ∆ ˜ .
Ilarge ,∆
i∈Ismall
The claim follows directly.
• The weakened KC inequality (5.1) is valid for φIlarge ,∆˜ ([0, 1]n ). Remember that D − ∆˜ > s(Ilarge ∩ A).
Thus every x ∈ {0, 1}n such that
∑ si xi ⩾ D − ∆˜
i∈Ilarge
satisfies the inequality
∑ xi ⩾ 1 .
i:ai =0,i∈Ilarge
Since this last inequality is a pitch-1 inequality,10 it is valid for φIlarge ,∆˜ ([0, 1]n ), see [24]. Hence, for
each x ∈ φIlarge ,∆˜ ([0, 1]n ) we get
∑ s0i xi ⩾ ∑ s0i xi = ∑ Uxi ⩾ U ⩾ αU .
i:ai =0 i:ai =0,i∈Ilarge i:ai =0,i∈Ilarge
• The weakened KC inequality (5.1) is valid for
( )
n
[0, 1] ∩ x : ∑ si xi ⩾ ∆˜ .
i∈Ismall
10 The pitch of an inequality
∑ j∈J c j x j ≥ d is the smallest number p such that the inequality ∑ j∈J c j ≥ d holds for every
J ⊆ supp(c) ⊆ [n] with |J| ≥ p.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 23
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
For each ( )
x ∈ [0, 1]n ∩ x : ∑ si xi ⩾ ∆˜
i∈Ismall
we have
∑ s0i xi ⩾ ∑ s0i xi = ∑ si xi ⩾ ∆˜ − s(Ismall ∩ A) ⩾ U − δ U
e ⩾ (1 − δ )U ⩾ αU .
i:ai =0 i:ai =0,i∈Ismall i:ai =0,i∈Ismall
Above, the second inequality follows from ∑i∈Ismall si xi ⩾ ∆˜ and −xi ⩾ −1 for i ∈ Ismall ∩ A.
6 Conclusion
After the recent series of strong negative results on extended formulations, we have presented a positive
result inspired by a connection to monotone circuits. Namely, we obtain the first quasi-polynomial-size
LP relaxation of min-knapsack with constant integrality gap from polylog-depth circuits for weighted
threshold functions.
This result sheds new light on the approximability of min-knapsack via small LPs by connecting it
to the complexity of monotone circuits. For instance, it follows from our results that proving that no
nO(1) -size LP relaxation for min-knapsack can have integrality gap at most α for some α > 2 would
rule out the existence of O(log n)-depth monotone circuits with bounded fan-in for weighted threshold
functions on n inputs, which is an open problem.
Acknowledgements
We thank the anonymous SODA reviewers and ToC reviewers for their valuable comments on the
conference version and the journal version of this paper, respectively.
References
[1] M IKLÓS A JTAI , J ÁNOS KOMLÓS , AND E NDRE S ZEMERÉDI: Sorting in c log n parallel steps.
Combinatorica, 3(1):1–19, 1983. [doi:10.1007/BF02579338] 11
[2] H YUNG -C HAN A N , M OHIT S INGH , AND O LA S VENSSON: LP-based algorithms for Capacitated
Facility Location. SIAM J. Comput., 46(1):272–306, 2017. Conference version in FOCS’14.
[doi:10.1137/151002320] 2
[3] E GON BALAS: Facets of the knapsack polytope. Mathematical Programming, 8(1):146–164, 1975.
[doi:10.1007/BF01580440] 3
[4] N IKHIL BANSAL , N IV B UCHBINDER , AND J OSEPH (S EFFI ) NAOR: Randomized competitive
algorithms for generalized caching. SIAM J. Comput., 41(2):391–414, 2012. Conference version in
STOC’08. [doi:10.1137/090779000] 5
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 24
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
[5] N IKHIL BANSAL , A NUPAM G UPTA , AND R AVISHANKAR K RISHNASWAMY: A constant factor
approximation algorithm for generalized min-sum set cover. In Proc. 21st Ann. ACM-SIAM Symp.
on Discrete Algorithms (SODA’10), pp. 1539–1545, 2010. [doi:10.1137/1.9781611973075.125] 5
[6] N IKHIL BANSAL AND K IRK P RUHS: The geometry of scheduling. SIAM J. Comput., 43(5):1684–
1698, 2014. Conference version in FOCS’10. [doi:10.1137/130911317, arXiv:1008.4889] 2, 5,
6
[7] A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON: Small extended
formulation for knapsack cover inequalities from monotone circuits. In Proc. 28th Ann. ACM-SIAM
Symp. on Discrete Algorithms (SODA’17), pp. 2326–2341, 2000. ACM DL. 1
[8] A BBAS BAZZI , S AMUEL F IORINI , S EBASTIAN P OKUTTA , AND O LA S VENSSON: No small linear
program approximates Vertex Cover within a factor of 2 − ε. Math. Oper. Res., 2018. Conference
version in FOCS’15. [doi:10.1287/moor.2017.0918, arXiv:1503.00753] 6
[9] A MOS B EIMEL AND E NAV W EINREB: Monotone circuits for weighted threshold functions.
In Proc. 20th IEEE Conf. on Computational Complexity (CCC’05), pp. 67–75. IEEE, 2005.
[doi:10.1109/CCC.2005.12] 8
[10] A MOS B EIMEL AND E NAV W EINREB: Monotone circuits for monotone weighted thresh-
old functions. Inform. Process. Lett., 97(1):12–18, 2006. Conference version in CCC’05.
[doi:10.1016/j.ipl.2005.09.008] 5, 8
[11] DANIEL B IENSTOCK: Approximate formulations for 0-1 knapsack sets. Oper. Res. Lett., 36(3):317–
320, 2008. [doi:10.1016/j.orl.2007.09.003] 3
[12] DANIEL B IENSTOCK AND B ENJAMIN M C C LOSKY: Tightening simple mixed-integer sets with
guaranteed bounds. Math. Program., 133(1-2):337–363, 2012. [doi:10.1007/s10107-010-0435-x] 3
[13] G ÁBOR B RAUN , S AMUEL F IORINI , S EBASTIAN P OKUTTA , AND DAVID S TEURER: Approxi-
mation limits of linear programs (beyond hierarchies). Math. Oper. Res., 40(3):513–796, 2015.
Conference version in FOCS’12. [doi:10.1287/moor.2014.0694, arXiv:1204.0957] 6, 8
[14] T IM C ARNES AND DAVID B. S HMOYS: Primal-dual schema for capacitated covering problems.
Math. Program., 153(2):289–308, 2015. Conference version in IPCO’08. [doi:10.1007/s10107-014-
0803-z] 5, 6, 14, 15
[15] ROBERT D. C ARR , L ISA K. F LEISCHER , V ITUS J. L EUNG , AND C YNTHIA A. P HILLIPS:
Strengthening integrality gaps for capacitated network design and covering problems. In Proc. 11th
Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’00), pp. 106–115, 2000. ACM DL. 3, 5, 6,
11, 14
[16] D EEPARNAB C HAKRABARTY, E LYOT G RANT, AND J OCHEN KÖNEMANN: On column restricted
and priority integer covering programs. In Proc. 14th Ann. Conf. on Integer Programming and Com-
binatorial Optimization (IPCO ’10), 2010. [doi:10.1007/978-3-642-13036-6_27, arXiv:1003.1507]
5
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 25
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
[17] S IU O N C HAN , JAMES L EE , P RASAD R AGHAVENDRA , AND DAVID S TEURER: Approximate
constraint satisfaction requires large LP relaxations. J. ACM, 63(4):34:1–34:22, 2016. Conference
version in FOCS’13. [doi:10.1145/2811255] 6
[18] X I C HEN , I GOR C ARBONI O LIVEIRA , AND ROCCO A. S ERVEDIO: Addition is exponentially
harder than counting for shallow monotone circuits. In Proc. 49th STOC, pp. 1232–1245, 2017.
[doi:10.1145/3055399.3055425, arXiv:1508.03061] 8
[19] M AURICE C HEUNG , J ULIÁN M ESTRE , DAVID B. S HMOYS , AND J OSÉ V ERSCHAE: A primal-
dual approximation algorithm for min-sum single-machine scheduling problems. SIAM J. Discrete
Math., 31(2):825–838, 2017. [doi:10.1137/16M1086819, arXiv:1612.03339] 5, 6
[20] M AURICE C HEUNG AND DAVID B. S HMOYS: A primal-dual approximation algorithm for min-sum
single-machine scheduling problems. In APPROX’11, pp. 135–146, 2011. [doi:10.1007/978-3-642-
22935-0_12] 5
[21] M ICHELE C ONFORTI , G ÉRARD C ORNUÉJOLS , AND G IACOMO Z AMBELLI: Extended formula-
tions in combinatorial optimization. 4OR, 8(1):1–48, 2010. [doi:10.1007/s10288-010-0122-z] 3,
23
[22] H OSSEIN E FSANDIARI , M OHAMMAD TAGHI H AJIAGHAYI , J OCHEN K ÖNEMANN , H AMID
M AHINI , DAVID L. M ALEC , AND L AURA S ANITÀ: Approximate deadline-scheduling with
precedence constraints. In Proc. 23rd Ann. European Symp. on Algorithms (ESA’15), pp. 483–495.
Springer, 2015. [doi:10.1007/978-3-662-48350-3_41, arXiv:1507.00748] 5, 6
[23] Y URI FAENZA , S AMUEL F IORINI , ROLAND G RAPPE , AND H ANS R AJ T IWARY: Extended
formulations, non-negative factorizations and randomized communication protocols. Math. Pro-
gram., 153(1):75–94, 2015. Conference version in ISCO’12. [doi:10.1007/s10107-014-0755-3,
arXiv:1105.4127] 8
[24] S AMUEL F IORINI , T ONY H UYNH , AND S TEFAN W ELTGE: Strengthening convex relaxations of
0/1-sets using Boolean formulas. 2017. [arXiv:1711.01358] 7, 21, 22, 23
[25] S AMUEL F IORINI , S ERGE M ASSAR , S EBASTIAN P OKUTTA , H ANS R AJ T IWARY, AND RONALD
DE W OLF : Exponential lower bounds for polytopes in combinatorial optimization. J. ACM,
62(2):17:1–17:23, 2015. Conference version in STOC’12. [doi:10.1145/2716307] 6
[26] M IKA G ÖÖS , R AHUL JAIN , AND T HOMAS WATSON: Extension complexity of independent
set polytopes. SIAM J. Comput., 47(1):241–269, 2018. Conference version in FOCS’16.
[doi:10.1137/16M109884X, arXiv:1604.07062] 4
[27] P ETER L. H AMMER , E LLIS L. J OHNSON , AND U RI N. P ELED: Facet of regular 0-1 polytopes.
Math. Program., 8(1):179–206, 1975. [doi:10.1007/BF01580442] 3
[28] PAVEL H RUBEŠ: On the nonnegative rank of distance matrices. Inform. Process. Lett., 112(11):457–
461, 2012. [doi:10.1016/j.ipl.2012.02.009] 4
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 26
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
[29] M AURICIO K ARCHMER AND AVI W IGDERSON: Monotone circuits for connectivity require super-
logarithmic depth. SIAM J. Discrete Math., 3(2):255–265, 1990. Conference version in STOC’88.
[doi:10.1137/0403021] 5, 8, 9
[30] R ICHARD M. K ARP: Reducibility among combinatorial problems. In R. E. M ILLER AND J. W.
T HATCHER, editors, Complexity of Computer Computations, pp. 85–103. Plenum Press, New York,
1972. PDF. [doi:10.1007/978-1-4684-2001-2_9] 2
[31] E UGENE L. L AWLER: Fast approximation algorithms for knapsack problems. Math. Oper. Res.,
4(2):339–356, 1979. Conference version in FOCS’77. [doi:10.1287/moor.4.4.339] 2
[32] JAMES R. L EE , P RASAD R AGHAVENDRA , AND DAVID S TEURER: Lower bounds on the
size of semidefinite programming relaxations. In Proc. 47th STOC, pp. 567–576, 2015.
[doi:10.1145/2746539.2746599] 6
[33] R ETSEF L EVI , A NDREA L ODI , AND M AXIM S VIRIDENKO: Approximation algorithms for the
capacitated multi-item lot-sizing problem via flow-cover inequalities. Math. Oper. Res., 33(2):461–
474, 2008. Conference version in IPCO’07. [doi:10.1287/moor.1070.0305] 5
[34] J ULIÁN M ESTRE AND J OSÉ V ERSCHAE: A 4-approximation for scheduling on a single machine
with general cost function. CoRR, 2014. [arXiv:1403.0298] 5
[35] S ABURO M UROGA: Threshold Logic and Its Applications. Wiley-Interscience, 1971. 11
[36] S ABURO M UROGA , I WAO T ODA , AND S ATORU TAKASU: Theory of majority decision elements.
J. Franklin Institute, 271(5):376–418, 1961. [doi:10.1016/0016-0032(61)90702-5] 11
[37] M ANFRED W. PADBERG , T ONY J. VAN ROY, AND L AURENCE A. W OLSEY: Valid inequalities
for fixed charge problems. Operations Research, 33(4):842–861, 1985. [doi:10.1287/opre.33.4.842]
2
[38] S EBASTIAN P OKUTTA AND M ATHIEU VAN V YVE: A note on the extension complexity of the
knapsack polytope. Oper. Res. Lett., 41(4):347–350, 2013. [doi:10.1016/j.orl.2013.03.010] 6
[39] T HOMAS ROTHVOSS: The matching polytope has exponential extension complexity. J. ACM,
64(6):41:1–41:19, 2017. Conference version in STOC’14. [doi:10.1145/3127497, arXiv:1311.2369]
6
[40] L AURENCE A. W OLSEY: Faces for a linear inequality in 0-1 variables. Math. Program., 8(1):165–
178, 1975. [doi:10.1007/BF01580441] 3
[41] M IHALIS YANNAKAKIS: Expressing combinatorial optimization problems by linear programs. J.
Comput. System Sci., 43(3):441–466, 1991. Conference version in STOC’88. [doi:10.1016/0022-
0000(91)90024-Y] 4, 7, 8
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 27
A BBAS BAZZI , S AMUEL F IORINI , S ANGXIA H UANG , AND O LA S VENSSON
AUTHORS
Abbas Bazzi
Software engineer
Google, Zürich, Switzerland
bazzi google com
Samuel Fiorini
Associate professor
Université libre de Bruxelles
Brussels, Belgium
sfiorini ulb ac be
http://homepages.ulb.ac.be/~sfiorini/
Sangxia Huang
Research scientist
Sony Mobile Communications
Lund, Sweden
huang sangxia gmail com
http://huang.sangxia.info/home
Ola Svensson
Assistant professor
EPFL, Lausanne, Switzerland
ola svensson epfl ch
http://theory.epfl.ch/osven/
ABOUT THE AUTHORS
A BBAS BAZZI graduated from EPFL in 2017; his advisor was Ola Svensson. His thesis
focused on the strength and limitations of Linear Programming relaxations. After
finishing his Ph. D., he joined Google Zürich as Software Engineer.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 28
S MALL E XTENDED F ORMULATION FOR K NAPSACK C OVER I NEQUALITIES FROM M ONOTONE C IRCUITS
S AMUEL F IORINI graduated from Université libre de Bruxelles (ULB, Brussels) in 2001
under the supervision of Jean-Paul Doignon. He has held research positions at CWI,
MIT, and GERAD - HEC Montreal. In 2005, he joined the faculty of the Department of
Mathematics and the Department of Computer Science at ULB. His research focuses on
combinatorial optimization, more precisely polyhedral combinatorics and approximation
algorithms. He is the principal investigator of the ERC grant FOREFRONT, focusing on
extended formulations. In addition to spending time with his family, windsurfing and
climbing bring balance to his life.
S ANGXIA H UANG graduated from KTH Royal Institute of Technology in 2015 under the
supervision of Johan Håstad. The topic of his thesis is hardness of approximation and
probabilistically checkable proofs. He worked as a postdoc at EPFL in Ola Svensson’s
group for two years. He then returned to Sweden and joined Sony Mobile Communica-
tions as a research engineer in machine learning.
O LA S VENSSON (not to be confused with the singer Ola Svensson) graduated from IDSIA
in 2009; his advisor was Monaldo Mastrolilli. The subject of his thesis was the approx-
imability of graph and scheduling problems. After spending two years as a postdoc
with Johan Håstad at KTH Royal Institute of Technology, Sweden, he is now back in
Switzerland as an assistant professor in the theory group at EPFL. Apart from doing
research, he enjoys the Alps that are in complete contrast to the flat but still beautiful
landscape in South Sweden where he grew up.
T HEORY OF C OMPUTING, Volume 14 (14), 2018, pp. 1–29 29