Approximation Limits of Linear Programs (Beyond Hierarchies)

Introduction

Linear programs (LPs) play a central role in the design of approximation algorithms, see, e.g., (Vazirani, 2001; Williamson and Shmoys, 2011; Lau et al., 2011). Therefore, understanding the limitations of LPs as tools for designing approximation algorithms is an important question.

The first generation of results studied the limitations of specific LPs by seeking to determine their integrality gaps. The second generation of results, pioneered by Arora et al. (2002), studied the limitations of structured LPs such as those generated by lift-and-project procedures or hierarchies (e.g., Sherali and Adams (1990) and Lovász and Schrijver (1991)).

In this work, we start a third generation of results that apply to any LP for a given problem. For example, our lower bounds address the following question: Is there a polynomial-size linear programming relaxation $\mathsf{LP}_{n}$ for CLIQUE that achieves a $n^{\Theta(1)}$-approximation for all graphs with at most $n$ vertices? We develop a framework for reducing questions of this kind to lower bounds on the nonnegative rankThe nonnegative rank of a matrix $M$, denoted $\operatorname{rank}_{+}(M)$, is the minimum $r$ such that $M=TU$ where $T$ and $U$ are nonnegative matrices with $r$ columns and $r$ rows, respectively. of certain matrices associated to the problem, and then prove lower bounds for the matrices corresponding to CLIQUE.

The matrices studied here are related to the unique disjointness problem, a variant of the famous disjointness problem from communication complexity (see, e.g., Chattopadhyay and Pitassi (2010) for a survey). In the disjointness problem (DISJ), both Alice and Bob receive a subset of $[n]:=\{1,\ldots,n\}$. They have to determine whether the two subsets are disjoint. The unique disjointness problem (UDISJ) is the promise version of the disjointness problem where the two subsets are guaranteed to have at most one element in common. Denoting the binary encoding of the sets of Alice and Bob by $a,b\in\{0,1\}^{n}$, respectively, this amounts to computing the Boolean function $\text{UDISJ}(a,b)\coloneqq 1-a^{\intercal}b$ on the set of pairs $(a,b)\in\{0,1\}^{n}\times\{0,1\}^{n}$ with $a^{\intercal}b\in\{0,1\}$. Viewing it as a partial $2^{n}\times 2^{n}$ matrix, we call UDISJ the unique disjointness matrix.

It is known that the communication complexity of UDISJ is $\Omega(n)$ bits for deterministic, nondeterministic and even randomized communication protocols (Kalyanasundaram and Schnitger, 1992; Razborov, 1992; Bar-Yossef et al., 2004). One consequence of this is that the nonnegative rank of any matrix obtained from UDISJ by filling arbitrarily the blank entries (for pairs $(a,b)$ with $a^{\intercal}b>1$) and perhaps adding rows and/or columns is still $2^{\Omega(n)}$. Indeed: (i) the support of the resulting matrix has $\Omega(n)$ nondeterministic communication complexity because it contains UDISJ, (ii) for every matrix $M$, $\log\operatorname{rank}_{+}(M)$ is lower bounded by the nondeterministic communication complexity of (the support matrix of) $M$ (Yannakakis, 1991).

In a recent paper Fiorini et al. (2012) proved strong lower bounds on the size of LPs expressing the traveling salesman problem (TSP), or more precisely on the size of extended formulations of the TSP polytope (see Section 2 for definitions of concepts related to polyhedra, extended formulations and slack matrices). Their proof works by embedding UDISJ in a slack matrix of the TSP polytope of the complete graph on $\Theta(n^{2})$ vertices. This solved a question left open in Yannakakis (1991). We use a similar approach for approximate extended formulations. In case of CLIQUE, our approach requires lower bounds on the nonnegative rank of partial matrices obtained from the UDISJ matrix by adding a positive offset to all the entries.

Our results are closely related to previous work in communication complexity for the (unique) disjointness problem and related problems. Lower bounds of $\Omega(n)$ on the randomized, bounded error communication complexity of disjointness were established in Kalyanasundaram and Schnitger (1992). In Razborov (1992) the distributional complexity of unique disjointness problem was analyzed, which in particular implies the result of Kalyanasundaram and Schnitger (1992). In that famous paper, Razborov proved the following rectangle corruption lemma: for every large rectangle within UDISJ, the number of -entries is proportional to the number of $1$-entries.

The most recent proof that the randomized, bounded error communication complexity of DISJ is $\Omega(n)$ is due to Bar-Yossef et al. (2004) and is based on information theoretic arguments. This leads to a lower bound for randomized communication within a high-error regime, that is, when the error probability is close to $1/2$. Here we derive a strong generalization dealing with shifts for approximate EFs and we recover the high-error regime bound.

Similar to the level of a hierarchy, we have the notion of rank for the Lovász-Schrijver relaxation and rank correspond to a similar complexity measure as the level. The rank is the minimum number of application of the Lovász-Schrijver operator $N$ until we obtain the integral hull of the polytope under consideration. Rank lower bounds of $n$ for Lovász-Schrijver relaxations of CLIQUE have been obtained in Cook and Dash (2001); a similar result for Sherali-Adams hierarchy can be found in Laurent (2003).

In Singh and Talwar (2010) integrality gaps, after adding few rounds of Chvátal-Gomory cuts, have been studied for problems including $k$-CSP, Max CUT, VERTEX COVER, and UNIQUE LABEL COVER showing that in some cases (e.g., $k$-CSP) the gap can be significantly reduced whereas in most other cases the gap remains high.

In the context of SDP relaxations, in particular formulations derived from the Lovász-Schrijver $N_{+}$ hierarchies (see Lovász and Schrijver (1991)) and the Lasserre hierarchies (see Lasserre (2002)) there has been significant work in recent years. For example, Arora et al. (2009) obtained a $O(\sqrt{\log n})$ upper bound on a suitable SDP relaxation of SPARSEST CUT. For lower bounds in terms of rank, see e.g., Schoenebeck (2008) for the $k$-CSP in the Lasserre hierarchy or Schoenebeck et al. (2007) for VERTEX COVER in the semidefinite Lovász-Schrijver hierarchy. Motivated by the Unique Games Conjecture, several works studied upper and lower bounds for SDP hierarchy relaxations of Unique Games (see for example, Guruswami and Sinop (2011); Barak et al. (2011, 2012b, 2012a)).

Approximate extended formulations have been studied before, for specific problems, e.g., KNAPSACK in Bienstock (2008), or as a general tool, see Vyve and Wolsey (2006).

For recent results on computing the nonnegative rank see, e.g., Arora et al. (2012).

2 Contribution

The contribution of the present paper is threefold.

We develop a framework for proving lower bounds on the sizes of approximate EFs. Through a generalization of Yannakakis’s factorization theorem, we characterize the minimum size of a $\rho$-approximate extended formulations as the nonnegative rank of any slack matrix of a pair of nested polyhedra. Thus we reduce the task of proving approximation limits for LPs to the task of obtaining lower bounds on the nonnegative ranks of associated matrices. Typically, these matrices have no zeros, which renders it impossible to use nondeterministic communication complexity. We emphasize the fact that the results obtained within our framework are unconditional. In particular, they do not rely on P $\neq$ NP.

We extend Razborov’s rectangle corruption lemma to deal with shifts of the UDISJ matrix. As a consequence, we prove that the nonnegative rank of any matrix obtained from the UDISJ matrix by adding a constant offset to every entry is still $2^{\Omega(n)}$. Moreover, we show that the nonnegative rank is still $2^{\Omega(n^{2\epsilon})}$ when the offset is at most $n^{1/2-\epsilon}$. To our knowledge, these are the first strong lower bounds on the nonnegative rank of matrices that contain no zeros. Our extension of Razborov’s lemma allow us to recover known lower bounds for DISJ in the high-error regime of Bar-Yossef et al. (2004).

We obtain a strong hardness result for CLIQUE w.r.t. a natural linear encoding of the problem. From the results described above, we prove that the size of every $O(n^{1/2-\epsilon})$-approximate EF for CLIQUE is $2^{\Omega(n^{2\epsilon})}$. Finally, we observe that the same bounds hold for approximations of SDPs by LPs. This suggests that SDP-based approximation algorithms can be significantly stronger than LP-based approximation algorithms. The inapproximability of SDPs by LPs has some interesting consequences. In particular we cannot expect to convert SDP-based approximation algorithms into LP-based ones by approximating the PSD-cone via linear programming.

We point out that our framework readily generalizes to SDPs by replacing nonnegative rank with PSD rank (see Gouveia et al. (2013a) for a definition of the PSD rank). However, no strong bound on PSD rank seems to be currently in sight.

Finally, we report that the results of this paper have inspired further research.

Braverman and Moitra (2013) improved our lower bound on the nonnegative rank of shifted UDISJ matrices and obtain super-polynomial lower bounds for shifts up to $O(n^{1-\epsilon})$, hence matching the algorithmic hardness of approximation for CLIQUE. This was achieved by pioneering information-theoretic methods for proving lower bounds on the nonnegative rank. An alternative information theoretic approach for lower bounding the nonnegative rank which simplifies and slightly improves the results in Braverman and Moitra (2013) has been presented in Braun and Pokutta (2013). This last paper also establishes that matrices obtained from shifts of UDISJ by removing rows and columns, or flipping entries, still have high nonnegative rank.

Chan et al. (2013) obtain lower bounds on the size of LPs approximating Max CSP. In particular, they prove that approximating Max CUT (with nonnegative weights) with a constant factor less than $2$ requires $n^{\Omega(\log n/\log\log n)}$. This solves a conjecture we stated in an earlier version of this text.

Rothvoß (2014) proved a $2^{\Omega(n)}$ lower bound on the nonnegative rank of the slack matrix of the perfect matching polytope by a significant modification of Razborov’s lemma. This exciting result essentially proves that there are is no small LP that can solve all weighted instance of the matching problem on a $n$-vertex complete graph.

3 Outline

We begin in Section 2 by setting up our framework for studying approximate extended formulations of combinatorial optimization problems. Then we extend Razborov’s rectangle corruption lemma in Section 3 and use this to prove strong lower bounds on the nonnegative rank of shifts of the UDISJ matrix. Finally, we draw consequences for CLIQUE and approximations of SDPs by LPs in Section 4.

Framework for Approximation Limits of LPs

In this section we establish our framework for studying approximation limits of LPs. First, we define in details the concepts of linear encodings and approximate extended formulations. Second, we prove a factorization theorem for pairs of nested polyhedra reducing existential questions on approximate extended formulations to the computation of nonnegative ranks of corresponding slack matrices.

For more about convex polytopes and polyhedra, see the standard reference Ziegler (1995).

2 Linear Encodings of Problems and Approximate EFs

For every fixed dimension $d$, a linear encoding $(\mathcal{L},\mathcal{O})$ naturally defines a pair of nested convex sets $P\subseteq Q$ where

This is equivalent to $P\subseteq K\subseteq\rho^{-1}Q$.

We return to Example 1. It is known that the Held-Karp relaxation $K$ of the metric TSP has integrality gap at most $3/2$ (see Held and Karp (1970), Wolsey (1980)). In geometric terms, this means that $P\subseteq K\subseteq 2/3\cdot Q$. Although $K$ is defined by an exponential number of inequalities, it is known that it can be reformulated with a polynomial number of constraints by adding a polynomial number of variables, see, e.g., Carr et al. (2009). That is, the Held-Karp relaxation $K$ has a polynomial-size extended formulation. Thus, the pair $(\mathcal{L},\mathcal{O})$ for the metric TSP has a polynomial-size $3/2$-approximate EF.

We require the following faithfulness condition: every instance of the problem can be mapped to an instance of the linear encoding in such a way that feasible solutions to an instance of the problem can be converted in polynomial time to feasible solutions to the corresponding instance of the linear encoding without deteriorating their objective function values, and vice-versa. Roughly speaking, we ask that each instance of the problem can be encoded as an instance of the linear encoding.

For linear encoding of graph problems, such as the maximum clique problem (CLIQUE), the set of feasible solutions is not allowed to depend on the input graph, which therefore must be encoded solely in the objective function. The set of feasible solutions is only allowed to depend on the size $n$ of the ground set.

The pair $(\mathcal{L},\mathcal{O})$ defines a linear encoding of Max $k$-SAT because each instance of Max $k$-SAT can be encoded as an instance of $(\mathcal{L},\mathcal{O})$. More precisely, to any given set of clauses over $n$ variables, we can associate a dimension $d=\Theta(n^{k})$ and weight vector $w\in\{0,1\}^{d}$ such that maximizing $\sum w_{C}x_{C}$ for $x\in\mathcal{L}\cap\{0,1\}^{d}$ corresponds to finding a truth assignment that maximizes the number of satisfied clauses.

Finally, we remark that the EF defined by the inequalities $0\leqslant x_{C}\leqslant 1$ and $x_{C}\leqslant\sum_{u_{i}\in C}x_{\{u_{i}\}}+\sum_{\bar{u}_{i}\in C}(1-x_{\{u_{i}\}})$ for all clauses $C$ is a polynomial-size $4/3$-approximate EF for Max $k$-SAT, as follows from Goemans and Williamson (1994).

3 Factorization Theorem for Pairs of Nested Polyhedra

A rank-$r$ nonnegative factorization of an $m\times n$ matrix $M$ is a decomposition of $M$ as a product $M=TU$ of nonnegative matrices $T$ and $U$ of sizes $m\times r$ and $r\times n$, respectively. The nonnegative rank $\operatorname{rank}_{+}(M)$ of $M$ is the minimum rank $r$ of nonnegative factorizations of $M$. In case $M$ is zero, we let $\operatorname{rank}_{+}(M)=0$. It is quite useful to notice that the nonnegative rank of $M$ is also the minimum number of nonnegative rank-$1$ matrices whose sum is $M$. From this, we see immediately that the nonnegative rank of $M$ is at least the nonnegative rank of any of its submatrices.

Our first result gives an essentially exact characterization of $\operatorname{xc}(P,Q)$ in terms of the nonnegative rank of the slack matrix of the pair $P,Q$. It states that the minimum extension complexity $\operatorname{xc}(P,Q)$ of a polyhedron sandwiched between $P$ and $Q$ equals the nonnegative rank of $S^{P,Q}$ (minus $1$, in some cases). The result readily generalizes Yannakakis’s factorization theorem (Yannakakis, 1991), which concerns the case $P=Q$. The idea of considering a pair $P,Q$ as we do here first appeared in Pashkovich (2012) and similar ideas appeared earlier in Gillis and Glineur (2012).

With the above notations, we have $\operatorname{rank}_{+}(S^{P,Q})-1\leqslant\operatorname{xc}(P,Q)\leqslant\operatorname{rank}_{+}(S^{P,Q})$ for every slack matrix of the pair $P,Q$. If the affine hull of $P$ is not contained in $Q$ and $\operatorname{rec}\left(Q\right)$ is not full-dimensional, we have $\operatorname{xc}(P,Q)=\operatorname{rank}_{+}(S^{P,Q})$. In particular, this holds when $P$ and $Q$ are polytopes of dimension at least $1$.

First, we deal with degenerate cases. Observe that $\operatorname{xc}(P,Q)=0$ if and only if there exists an affine subspace containing $P$ and contained in $Q$, that is, if and only if the affine hull of $P$ is contained in $Q$. In this case, we have $\operatorname{rank}_{+}(S^{P,Q})\in\{0,1\}$, so the theorem holds.

Now assume that the affine hull of $P$ is not contained in $Q$. Then, $\operatorname{rank}_{+}(S^{P,Q})\geqslant 1$ because having $\operatorname{rank}_{+}(S^{P,Q})=0$ means either that $S^{P,Q}$ is empty, that is, $m=0$ or $n+k=0$, or that $S^{P,Q}$ is the zero matrix. In all cases, this contradicts our assumption that the affine hull of $P$ is not contained in $Q$.

Thus we obtain that (7) is a size-$r$ EF of the pair $P,Q$. Therefore, $\operatorname{xc}(P,Q)\leqslant\operatorname{rank}_{+}(S^{P,Q})$.

Finally, when $\operatorname{rec}\left(Q\right)$ is not full-dimensional, then $c$ above can be chosen to be $\mathbf{0}$. This simplifies the factorization, and yields the sharper inequality $\operatorname{rank}_{+}(S^{P,Q})\leqslant\operatorname{xc}(P,Q)$. ∎

Theorem 1 directly yields the following result.

Fixing $\rho\geqslant 1$, Theorem 2 characterizes the minimum number of inequalities in any LP providing a $\rho$-approximation for the problem under consideration. We point out that the theorem directly generalizes to SDPs, by replacing nonnegative rank by PSD rank (Gouveia et al., 2013a). Here, we focus on LPs and nonnegative rank. As a matter of fact, strong lower bounds on the PSD rank seem to be currently lacking.

4 A Problem with no Polynomial-Size Approximate EF

A related object is the cut cone, defined as the cone generated by the cut-vectors $\chi^{\delta(X)}$:

Consider the maximum cut problem (Max CUT) with arbitrary weights, and its usual linear encoding. With this encoding we have $P=Q=\operatorname{CUT}(n)$. Our next result states that this problem has no $\rho$-approximate EF, whatever $\rho\geqslant 1$ is. Intuitively, this phenomenon stems from the fact that, because $\mathbf{0}$ is a vertex of the cut polytope, every approximate EF necessarily ‘captures’ all facets of the cut polytope incident to $\mathbf{0}$ (see Figure 1). These facets define the cut cone, which turns out to have high extension complexity. Although this follows rather easily from ideas of Fiorini et al. (2012), we include a proof here for completeness.

For every $\rho\geqslant 1$, every $\rho$-approximate EF of the Max CUT problem with arbitrary weights has size $2^{\Omega(n)}$. More precisely, disregarding the value of $\rho\geqslant 1$, we have $\operatorname{xc}(\operatorname{CUT}(n),\rho\operatorname{CUT}(n))=2^{\Omega(n)}$.

Let $Ex+Fy=g$, $y\geqslant\mathbf{0}$ denote a minimum size $\rho$-approximate EF of $\operatorname{CUT}(n)$. We claim that

is an EF of the cut cone. Let $K$ be the polyhedron obtained by projecting the set of solutions of (9) into $x$-space. Clearly, $K$ is a cone containing all the cut-vectors $\chi^{\delta(X)}$, from which we get that $\operatorname{CUT-CONE}(n)\subseteq K$. Now take any point $(x,y,\lambda)$ satisfying (9). If $\lambda=0$ then necessarily $x=\mathbf{0}$ because $Ex+Fy=\mathbf{0}$, $y\geqslant\mathbf{0}$ defines the recession cone of a polyhedron that projects into $\rho\operatorname{CUT}(n)$, which is bounded. In this case we have $x=\mathbf{0}\in\operatorname{CUT-CONE}(n)$. Assume that $\lambda>0$. Then $E\lambda^{-1}x+F\lambda^{-1}y=g$ and $\lambda^{-1}y\geqslant\mathbf{0}$ which implies that $\lambda^{-1}x$ is in $\rho\operatorname{CUT}(n)$. Thus $\rho^{-1}\lambda^{-1}x$ is in $\operatorname{CUT}(n)$ and $x$ is thus a positive combination of cut-vectors, hence $x\in\operatorname{CUT-CONE}(n)$. This yields $K\subseteq\operatorname{CUT-CONE}(n)$. In conclusion, $K=\operatorname{CUT-CONE}(n)$ and (9) is an EF of the cut cone. The size of this EF is at most $r+1$, where $r$ denotes the size of the given $\rho$-approximate EF of $\operatorname{CUT}(n)$. Thus $\operatorname{xc}(\operatorname{CUT-CONE}(n))\leqslant r+1$.

By using the correlation mapping (see (Laurent and Deza, 1997, p. 55)), the cut cone has the same extension complexity as its corresponding correlation cone, defined as

We claim that the unique disjointness matrix on $[n-2]$ can be embedded in a slack matrix of $\operatorname{COR-CONE}(n-1)$. To prove this, consider the $(n-1)\times(n-1)$ rank-$1$ positive semidefinite matrices

where $a,b\in\{0,1\}^{n-2}$. The Frobenius inner product $\langle T_{a},z\rangle\geqslant 0$ of $T_{a}$ with any correlation matrix $z=\binom{b_{0}}{b}\binom{b_{0}}{b}^{\intercal}$ is nonnegative because both matrices are positive semidefinite. Thus $\langle T_{a},z\rangle\geqslant 0$ is valid for all points $z\in\operatorname{COR-CONE}(n-1)$, for all $a\in\{0,1\}^{n-2}$. Moreover, $\langle T_{a},U^{b}\rangle=(1-a^{\intercal}b)^{2}$ for all $a,b\in\{0,1\}^{n-2}$ and thus $\langle T_{a},U^{b}\rangle=\text{UDISJ}(a,b)$ provided $a^{\intercal}b\in\{0,1\}$.

From what precedes, the slack of correlation matrix $U^{b}$ with respect to the valid inequality $\langle T_{a},z\rangle\geqslant 0$ is $\text{UDISJ}(a,b)$ provided $a^{\intercal}b\in\{0,1\}$. Therefore, $\operatorname{COR-CONE}(n-1)$ has a slack matrix that contains UDISJ on $[n-2]$. Because the nonnegative rank of any matrix containing UDISJ is $2^{\Omega(n)}$ (this follows from (Razborov, 1992), see (Fiorini et al., 2012, Theorem 1)), we conclude that the nonnegative rank of some slack matrix of $\operatorname{COR-CONE}(n-1)$ is $2^{\Omega(n)}$. From Theorem 1 applied to $P=Q=\operatorname{COR-CONE}(n-1)$, it follows that $\operatorname{xc}(\operatorname{COR-CONE}(n-1))=2^{\Omega(n)}$. Thus we get

from which we obtain $r=2^{\Omega(n)}$. The result then follows immediately. ∎

Extension of Razborov’s Lemma and Shifts of Unique Disjointness

In the first subsection we generalize Razborov’s famous lemma on the disjointness problem (see Razborov (1992) or Kushilevitz and Nisan (1997, Lemma 4.49) for the original version). In the next subsection we apply it to shift the UDISJ matrix without significantly decreasing its nonnegative rank, which will be used in later sections to obtain lower bounds on approximate extended formulations.

The main improvements to Razborov’s lemma are threefold: 1. the dependence on the error parameter $\epsilon$ is made explicit; 2. better analytical estimations are employed to improve overall strength of the statement; 3. probabilities are generalized to expected values to homogenize the proof and yield a stronger lemma.

Let us write $I_{C}$ for the indicator of an event $C$. In case $f$ and $g$ are both binary, $X$ is the indicator of a rectangle $R$, that is $X=I_{R}$, and (11) becomes

which is a strengthened version of Razborov’s original lemma.

For concreteness, the reader might find it helpful to imagine that $X$ is the indicator of a rectangle in the proof below. Our proof is inspired by the version in Kushilevitz and Nisan (1997, Lemma 4.49) and we adopt similar notations.

This brings the advantage of the following alternative description of $\mu$.

We note the following nice interpretation of $\operatorname{Row}_{0}(T)+\operatorname{Row}_{1}(T)$ and $\operatorname{Col}_{0}(T)+\operatorname{Col}_{1}(T)$, that we will use at the end of the proof:

Note that: 1. the distribution of $(a,b)$ conditioned on a given $T$ is a product distribution (this local independence property is the main reason why we reinterpret the distribution $\mu$); 2. the marginal distributions of $a$ conditioned on $(T,i\in a,i\in b)$ and $(T,i\in a)$ are the same (and similarly for $b$, we can remove the condition $i\in a$). From these facts, we get

Exchanging the roles of rows and columns, we have

In Step 3 below, we will define two events, $\operatorname{row-big}(T)$ and $\operatorname{column-big}(T)$. The event $\operatorname{small}(T)$ holds if and only if not both of $\operatorname{row-big}(T)$ and $\operatorname{column-big}(T)$ hold. Thus

By (16), (27) and (29), these upper bounds imply

from which the result clearly follows, by rearranging.

(This holds when $f(a)$ is replaced by any function of $a$.)

We now estimate the entropy of $s$. On the one hand, by subadditivity of the entropy, we get the following upperbound on $H\left(s\,\middle|\,T_{2}\right)$:

In this last equation, $H\left(\lambda\right)$ denotes the binary entropy of $\lambda$. On the other hand, we get a lower bound on $H\left(s\,\middle|\,T_{2}\right)$ from our upper bound on the distribution of $s$ (which induces “flatness” of the distribution):

To estimate this expression, we use the Taylor expansion of the binary entropy function at $1/2$:

We require $\frac{\epsilon}{2}=2\sqrt{\delta^{\prime}}$, from which we express $\delta$ in terms of $\epsilon$ using (50):

This concludes the proof of (34). Equation (33) follows by exchanging rows and columns.

Step 4: Error estimation in the “small” case. Suppose that for some given $T$, $\operatorname{small}(T)$ holds because $\operatorname{row-big}(T)$ does not hold (the argument is similar in case $\operatorname{column-big}(T)$ does not hold). Then, using (14),

2 Lower Bounds for Shifts of Unique Disjointness

If $\rho$ is a fixed constant, then $\operatorname{rank}_{+}(M)=2^{\Omega(n)}$.

If $\rho=O(n^{\beta})$ for some constant $\beta<1/2$ then $\operatorname{rank}_{+}(M)=2^{\Omega(n^{1-2\beta})}$.

On the other hand, by applying Lemma 4 to each $i\in[r]$ and summing up all equations we find

If $\rho$ is constant, this last expression is $2^{\Omega(n)}$ provided $\epsilon$ is chosen sufficiently close to . This proves part (i) of the theorem.

If $\rho\leqslant Cn^{\beta}$ for some positive constant $C$, then we can take $\epsilon=\frac{1}{2Cn^{\beta}}$. Thus $\frac{1}{\rho}-\epsilon\geqslant\frac{1}{2Cn^{\beta}}=\Omega(n^{-\beta})$. This leads to the lower bound $r\geqslant 2^{\Omega(n^{1-2\beta})}$ as claimed in part (ii). ∎

Polyhedral Inapproximability of CLIQUE and SDPs

We will now use Theorem 5 in combination with Theorem 2 to lower bound the sizes of approximate EFs for CLIQUE and some SDPs. First, we pinpoint a pair $P,Q$ of nested polyhedra that will be the source of our polyhedral inapproximability results. Second, we give a faithful linear encoding of CLIQUE and prove strong lower bounds on the sizes of approximate EFs for CLIQUE w.r.t. this encoding. Third, we focus on approximations of SDPs by LPs.

Let $n$ be a positive integer. The correlation polytope $\operatorname{COR}(n)$ is defined as the convex hull of all the $n\times n$ rank-$1$ binary matrices of the form $bb^{\intercal}$ where $b\in\{0,1\}^{n}$. In other words,

This will be our inner polytope $P$. Next, let

where $\langle\cdot,\cdot\rangle$ denotes the Frobenius inner product. This will be our outer polyhedron $Q$.

Then the following is known, see (Fiorini et al., 2012). First, $P\subseteq Q$. Second, denoting by $S^{P,Q}$ the slack matrix of the pair $P,Q$, we have $S^{P,Q}_{ab}=(1-a^{\intercal}b)^{2}$. Thus, for $\rho\geqslant 1$, we have $S^{P,\rho Q}_{ab}=(1-a^{\intercal}b)^{2}+\rho-1$. Observe that the matrix $S^{P,\rho Q}$ is a $\rho$-extension of UDISJ and therefore has high nonnegative rank via Theorem 5; moreover it has positive entries everywhere for $\rho>1$. Together with Theorem 1 this implies that every polyhedron sandwiched between $P=\operatorname{COR}(n)$ and $\rho Q$ has large extension complexity. We obtain the following theorem.

Let $\rho\geqslant 1$, let $n$ be a positive integer and let $P=\operatorname{COR}(n)$, $Q=Q(n)$ be as above. Then the following hold:

If $\rho$ is a fixed constant, then $\operatorname{xc}(P,\rho Q)=2^{\Omega(n)}$.

If $\rho=O(n^{\beta})$ for some constant $\beta<1/2$, then $\operatorname{xc}(P,\rho Q)=2^{\Omega(n^{1-2\beta})}$.

2 Polyhedral Inapproximability of CLIQUE

The admissible objective functions are chosen as follows to encode the CLIQUE problem for graphs $G$ supported on $[n]$. Given a graph $G$ such that $V(G)\subseteq[n]$, we let $w_{ii}\coloneqq 1$ for $i\in V(G)$, $w_{ii}\coloneqq 0$ for $i\in[n]\setminus V(G)$, $w_{ij}=w_{ji}\coloneqq-1$ when $ij$ is a non-edge of $G$ (that is, $i,j\in V(G)$, $i\neq j$ and $ij\notin E(G)$), and $w_{ij}=w_{ji}\coloneqq 0$ otherwise. We denote the resulting weight vector by $w^{G}$. Notice that for a graph $G$ with $V(G)=[n]$, we have $w^{G}=I-A(\overline{G})$ where $I$ is the $n\times n$ identity matrix, $A(\overline{G})$ is the adjacency matrix of the complement of $G$.

A feasible solution $x=bb^{\intercal}\in\{0,1\}^{n\times n}$ maximizes $\langle w^{G},x\rangle$ only if $b$ is the characteristic vector (or incidence vector) of a clique of $G$. Indeed, if $b=\chi^{X}$ and $ij$ is a non-edge of $G$ with $i,j\in X$ then removing $i$ or $j$ from $X$ increases $\langle w^{G},x\rangle$. Moreover, the maximum of $\langle w^{G},x\rangle$ over $x\in\{0,1\}^{n\times n}$ feasible is the clique number $\omega(G)$.

W.r.t. the linear encoding defined above, CLIQUE has an $O(n^{2})$-size $n$-approximate EF. Moreover, every $n^{1/2-\epsilon}$-approximate EF of CLIQUE has size $2^{\Omega(n^{2\epsilon})}$, for all $0<\epsilon<1/2$.

The $n$-approximate EF of CLIQUE is trivial: it is defined by the system $\mathbf{0}\leqslant x\leqslant\mathbf{1}$, or in slack form $x-y=\mathbf{0}$, $x+z=\mathbf{1}$, $y\geqslant\mathbf{0}$, $z\geqslant\mathbf{0}$. We claim that this defines a $n$-approximate EF of CLIQUE of size $2n^{2}$. Indeed, letting $K=^{n\times n}$ denote the polytope defined by this EF, we have $P\subseteq K$. Moreover, $\max\{\langle w,x\rangle\mid x\in K\}\leqslant n\leqslant n\cdot\max\{\langle w,x\rangle\mid x\in P\}$ for all admissible objective functions $w$ of dimension $n\times n$ with a nonzero diagonal. In case an admissible $w$ has $w_{ii}=0$ for all $i\in[n]$, we have $\max\{\langle w,x\rangle\mid x\in K\}=0=\max\{\langle w,x\rangle\mid x\in P\}$. Our claim and the first part of the theorem follows.

3 Polyhedral Inapproximability of SDPs

In this section we show that there exists a spectrahedron with small semidefinite extension complexity but high approximate extension complexity; i.e., any sufficiently fine polyhedral approximation is large. This indicates that in general it is not possible to approximate SDPs arbitrarily well using small LPs, so that SDPs are indeed a much stronger class of optimization problems. (The situation looks quite different for SOCPs, see Ben-Tal and Nemirovski (2001).) The result follows from Theorem 6 and Fiorini et al. (2012).

If $\rho$ is a fixed constant, then $\operatorname{xc}(K)=2^{\Omega(n)}$.

If $\rho=O(n^{\beta})$ for some constant $\beta<1/2$, then $\operatorname{xc}(K)=2^{\Omega(n^{1-2\beta})}$.

By Lemma 9, there is a spectrahedron $S$ with $P\subseteq S\subseteq Q$ and $\operatorname{xc}_{SDP}(S)\leqslant n+1$. We now show $S^{\rho-1}\subseteq\rho Q$. Let $x\in S^{\rho-1}$, and let $x_{0}\in S$ with $\|x-x_{0}\|_{1}\leq\rho-1$. As $S\subseteq Q$, we also have $x_{0}\in Q$, hence for every $a\in\{0,1\}^{n}$ we obtain

Therefore $x\in\rho Q$. Therefore, $S^{\rho-1}\subseteq\rho Q$ for $\rho\geqslant 1$. If now $K$ is a polyhedron such that $S\subseteq K\subseteq S^{\rho-1}$ then also $P\subseteq K\subseteq\rho Q$. The result thus follows from Theorem 6. ∎

Concluding Remarks

We have introduced a general framework to study approximation limits of small LP relaxations. Given a polyhedron $Q$ encoding admissible objective functions and a polytope $P$ encoding feasible solutions, we have proved that any LP relaxation sandwiched between $P$ and a dilate $\rho Q$ has extension complexity at least the nonnegative rank of the slack matrix of the pair $P$, $\rho Q$.

This yields a lower bound depending only on the linear encoding of the problem at hand, and applies independently of the structure of the actual relaxation. By doing so, we obtain unconditional lower bounds on integrality gaps for small LP relaxations, which hold even in the unlikely event that $P=NP$.

We have proved that every polynomial-size LP relaxation for (a natural linear encoding of) CLIQUE has essentially an $\Omega(\sqrt{n})$ integrality gap. As mentioned above, this was recently improved by Braverman and Moitra (2013) to a tight $\Omega(n^{1-\epsilon})$ integrality gap, see Braun and Pokutta (2013) for a short proof and many generalizations.

Finally, our work sheds more light on the inherent limitations of LPs in the context of combinatorial optimization and approximation algorithms, in particular, in comparison to SDPs. We provide strong evidence that certain approximation guarantees can only be achieved via non-LP-based techniques (e.g., SDP-based or combinatorial).

Actually, our work has inspired Chan et al. (2013) to prove lower bounds on the size of LPs for approximating Max CUT, Max $k$-SAT and in fact any Max CSP. Among other results, they obtain a $n^{\Omega(\log n/\log\log n)}$ lower bound on the size of any $(2-\epsilon)$-approximate EF for Max CUT (of course, with nonnegative weights). Chan et al. (2013) thus proving the following conjecture on Max CUT that we stated in an earlier version of this text:

Chan et al. (2013) It is not possible to approximate Max CUT with LPs of poly-size within a factor better than $2$.

This is in stark contrast with the ratio achieved by the SDP-based algorithm of Goemans and Williamson (1995) which is known to be optimal, assuming the Unique Games Conjecture Khot (2002); Khot et al. (2007); Mossel et al. (2005).

Finally, so far no strong lower bounding technique for semidefinite EFs are known. It is plausible that in the near future we will see lower bounding techniques on the PSD rank that would be suited for studying approximation limits of SDPs. (We remark however that such bounds should not only argue on the zero/nonzero pattern of a slack matrix.)

Acknowledgements

We would like to thank the two referees for their time and comments which contributed to improve the text.

References