Tag Archive

You are currently browsing the tag archive for the ‘Integrality gap’ tag.

On the Unique Games Conjecture (part 2)

November 20, 2010 in math, theory | Tags: Integrality gap, unique games | 3 comments

[I am preparing a survey talk on Unique Games for a mathematics conference, and writing a survey paper for a booklet that will be distributed at the conference. My first instinct was to write a one-line paper that would simply refer to Subhash's own excellent survey paper. Fearing that I might come off as lazy, I am instead writing my own paper. Here are some fragments. Comments are very welcome.]

1. Why is the Unique Games Conjecture Useful

In a previous post we stated the Unique Games Conjecture and made the following informal claim, here rephrased in abbreviated form:

To reduce Label Cover to a graph optimization problem like Max Cut, we map variables to collections of vertices and we map equations to collections of edges; then we show how to “encode” assignments to variables as 2-colorings of vertices which cut a ${\geq c_1}$ fraction of edges, and finally (this is the hardest part of the argument) we show that given a 2-coloring that cuts a ${\geq c_2}$ fraction of edges, then

the given 2-coloring must be somewhat “close” to a 2-coloring coming from the encoding of an assignment and

if we “decode” the given 2-coloring to an assignment to the variables, such an assignment satisfies a noticeable fraction of equations.

Starting our reduction from a Unique Game instead of a Label Cover problem, we only need to prove (1) above, and (2) more or less follows for free.

To verify this claim, we “axiomatize” the properties of a reduction that only achieves (1): we describe a reduction mapping a single variable to a graph, such that assignments to the variable are mapped to good cuts, and somewhat good cuts can be mapped back to assignments to the variable. The reader can then go back to our analysis of the Max Cut inapproximability proof in the previous post, and see that the properties below are sufficient to implement the reduction.

Read the rest of this entry »

Survey on Hardness of Approximation

February 21, 2010 in theory | Tags: Integrality gap, PCP, unique games | 13 comments

In 2004 I wrote a survey on hardness of approximation as a book chapter for a book on approximation algorithm. I have just prepared a revised version for a new edition of the book.

While it would have been preferable to rethink the organization and start from scratch, because of time constraints I was only able to add sections on integrality gaps and on unique games, and to add references to more recent work (e.g. the combinatorial proof of the PCP theorem, the new 2-query PCPs, the tight results on minimizing congestion in directed networks, and so on).

If your (or your friend’s) important results are not cited, do let me know. The deadline to submit the chapter has long passed, but the threats from the editor haven’t yet escalated to the point where I feel that I have to submit it or else.

How Good is the Leighton-Rao Relaxation?

June 4, 2008 in math, theory | Tags: Expanders, Integrality gap, Metric embeddings | Leave a comment

Continuing our seemingly never-ending series on approximations to edge expansion, we come to the question of how good is the Leighton-Rao relaxation.

Given a graph $G=(V,E)$ , we are trying to approximate the sparsest cut problem (which, in turn, approximates the edge expansion problem within a factor of two) defined as

$\displaystyle \phi(G) := \min_{S\subseteq V} \frac {edges(S,V-S)} {\frac 1n |S| \cdot |V-S|}$

And we have seen that an equivalent characterization of sparsest cut is:

$(1) \ \ \ \displaystyle \phi(G) = \min_{x\in {\mathbb R}^V} \frac{ \sum_{i,j} A(i,j) | x_i - x_j | } {\frac 1n \sum_{i,j} |x_i - x_j | }$

In the Leighton-Rao relaxation, we have

$(2) \ \ \ \displaystyle LR(G) := \min_{d\in {\cal M}(V)} \frac{ \sum_{i,j} A(i,j) d(i,j) }{\frac 1n \sum_{i,j} d(i,j)}$

where ${\cal M}(V)$ is the set of all semi-metrics $d: V \times V \rightarrow {\mathbb R}$ , that is, of all functions such that $d(i,j) = d(j,i) \geq 0$ , $d(i,i)=0$ , and that obey the “triangle inequality”

$d(i,j) \leq d(i,k) + d(k,j)$

for all $i,j,k \in V$ .

This is clearly a relaxation of the sparsest cut problem, because for every $x \in {\mathbb R}^V$ the “distances” $|x_i - x_j|$ define indeed a semi-metric over $V$ .

How bad can the relaxation be? Take a family of regular constant-degree expander graphs, that is graphs where $\phi$ is a constant and the degree $k$ is a constant independent of $n=|V|$ . Define $d(i,j)$ to be the shortest path distance between $i$ and $j$ in the graph. This is clearly a semi-metric, and we have

$\displaystyle \sum_{i,j} A(i,j) d(i,j) = kn = O(n)$

because along every edge the distance is precisely one, and

$\displaystyle \sum_{i,j} d(i,j) = \Omega (n^2 \log_k n)$

because, for every vertex $i$ , at most $k^t$ other vertices can be within
distance $t$ , and so at least half the vertices are at distance $\Omega( \log_k n)$ .

So we have

$\displaystyle LR(G) = O \left( \frac 1 {\log n} \right)$

even though $\phi(G) = \Omega(1)$ , so the error in the approximation can be as bad as a factor of $\log n$ . We shall prove that this is as bad as it gets.

Our task is then: given a feasible solution to (2), that is, a distance function defined on the vertices of $G$ , find a feasible solution to sparsest cut whose cost is as small as possible, and no more than a $O(\log n)$ factor off from the cost of the solution to (2) that we started from. Instead of directly looking for a cut, we shall look for a solution to (1), which is a more flexible formulation.

The general strategy will be, given $d$ , to find a distribution $X$ over vectors $x \in {\mathbb R}^V$ such that for every two vertices $i,j$ we have

$(3) \ \ \ \displaystyle \Omega\left( \frac {1}{\log n} \right) \cdot d(i,j) \leq {\mathbb E} | X_i - X_j | \leq d(i,j)$

Suppose that we start from a solution to (2) of cost $c$ , that is, we have a semimetric $d(\cdot,\cdot)$ such that

$\displaystyle \sum_{i,j} A_{i,j} d(i,j) = c \cdot \frac 1n \sum_{i,j} d(i,j)$

Then our distribution $X$ is such that

$\displaystyle {\mathbb E} \sum_{i,j} A_{i,j} |X_i - X_j| \leq \sum_{i,j} A_{i,j} d(i,j)$

and

$\displaystyle \sum_{i,j} d(i,j) \leq O \left( {\log n} \right) {\mathbb E} \sum_{i,j}|X_i - X_j|$

$\displaystyle {\mathbb E} \left[ \sum_{i,j} A_{i,j} |X_i - X_j| - O(c\log n) \cdot \frac 1n \sum_{i,j} |X_i - X_j| \right] \leq 0$

and there must exist a vector $x$ in the support of the distribution $X$ such that

$\displaystyle \sum_{i,j} A_{i,j} |x_i - x_j| - O(c\log n) \cdot \frac 1n \sum_{i,j} |x_i - x_j| \leq 0$

and now we are done because the cost of $x$ in (1) is at most $O(\log n)$ times the optimum of the Leighton-Rao relaxation.

Though this works, it seems an overkill to require condition (3) for all pairs of vertices. It seems sufficient to require

${\mathbb E} |X_i-X_j| \leq d(i,j)$

only for edges, and to require

$d(i,j) \leq O(\log n) \cdot {\mathbb E} |X_i-X_j|$

only “on average” over all pairs of vertices. It can be shown, however, that if one wants to round a generalization of the Leighton-Rao relaxation to sparsest cut with “non-uniform demands,” then any rounding algorithm can be turned into a rounding algorithm that satisfies (3).

So how do we start from an arbitrary metric and come up with a probabilistic linear order of the vertices so that their distances in the original metric are well approximated in the linear ordering? We will describe a method of Bourgain, whose applicability in this setting is due Linial, London and Rabinovich.

The starting point is to see that if $A$ is a set of vertices, and we define

$\displaystyle X_i := d(A,i) := \min_{a\in A} d(a,i)$

then, no matter how we choose $A$ , we always have

$|X_i - X_j | = |d(A,i) - d(A,j) | \leq d(i,j)$

[Hint: use the triangle inequality to see that $d(A,j) \leq d(A,i) + d(i,j)$ .]

This means that “all we have to do” is to find a distribution over sets $A$ such that for every $i,j$ we have

$(3) \ \ \ \displaystyle {\mathbb E} | d(A,i) - d(A,j) | \geq \Omega \left( \frac 1 {\log n} \right) \cdot d(i,j)$

If you want to make it sound more high-brow, you may call such a distribution a Frechet embedding of $d$ into $\ell_1$ . Constructing such a distribution will be the subject of the next post.

The Limitations of the Spectral Partitioning Algorithm

May 23, 2008 in math, theory | Tags: Expanders, Integrality gap, Spectral partitioning | Leave a comment

We continue to talk about the problem of estimating the expansion of a graph $G=(V,E)$ , focusing on the closely related sparsest cut, defined as

$\displaystyle \phi(G):= \min_{S} \frac {edges(S,V-S) } { \frac 1n \cdot |S| \cdot |V-S| }$

The spectral paritioning algorithm first finds a vector $x \in {\mathbb R}^n$ minimizing

$(1) \ \ \ \displaystyle \frac{ \sum_{i,j} A(i,j) |x(i)-x(j)|^2 } { \frac 1n \cdot \sum_{i,j} |x(i)-x(j)|^2}$

(where $A$ is the adjacency matrix of $G$ ) and then finds the best cut $(S,V-S)$ where $S$ is of the form $\{ i \in V: \ x(i) \geq t \}$ for a threshold $t$ .

We proved that if the quantity in (1) is $\epsilon$ and $G$ is $d$ -regular, then the algorithm will find a cut of sparsity at most $\sqrt{8 \epsilon d}$ , and that if $x$ is the eigenvector of the second eigenvalue, then it is an optimal solution to (1), and the cost of an optimal solution to (1) is a lower bound to $\phi(G)$ . This means that the algorithm finds a cut of sparsity at most $\sqrt{8 \phi(G) d}$ .

Can the analysis be improved? Read the rest of this entry »

The limitations of linear and semidefinite programming

October 18, 2006 in theory | Tags: Integrality gap | 3 comments

The fact that Linear Programming (LP) can be solved in polynomial time (and, also, efficiently in practice) and that it has such a rich geometric theory and such remarkable expressive power makes LP a powerful unifying concept in the theory of algorithms. It “explains” the existence of polynomial time algorithms for problems such as Shortest Paths and Min Cut, and if one thinks of the combinatorial algorithms for such problems as algorithms for the corresponding linear programs, one gains additional insights.

When looking for algorithms for a new combinatorial problem, a possible approach is to express the problem as a 0/1 integer program, then relax it to a linear program, by letting variables range between 0 and 1, and then hope for the best. “The best” being the lucky event that the value of the optimum of the relaxation is the same as that of the combinatorial program, or at least a close approximation. If one finds that, instead, the relaxation has optimal fractional solutions of cost very different from the combinatorial optimum, one may try to add further inequalities that are valid for 0/1 solutions and that rule out the problematic fractional solutions.

Many “P=NP” papers follow this approach, usually by presenting a polynomial-size linear programming relaxation of TSP and then “proving” that the optimum of the relaxation is the same as the combinatorial optimum. One can find recent examples here and here.

Similar results were “proved” in a notorious series of paper by Ted Swart in the mid 1980s. After counterexamples were found, he would revise the paper adding more inequalities that would rule out the counterexample.

Finally, Mihalis Yannakakis took matters into his own hands and proved that all “symmetric” relaxations of TSP of sub-exponential size have counterexamples on which the optimum of the relaxation is different from the combinatorial optimum. (All of the LPs suggested by Swart where “symmetric” according to Yannakakis’s definition.)

This is actually one of the few known lower bounds that actually applies to a “model of computation” capturing a general (and otherwise promising) class of algorithms.

(I first read about this story in Christos Papadimitriou’s complexity book, but I found the above references in Gerhard J Woeginger’s P versus NP page.)

In the theory of approximation algorithms, we have plenty of problems that are believed to be intractable but that are not known to be NP-hard, such as approximating Vertex Cover within a factor of 1.9, or approximating Sparsest Cut within a factor of 10. LP and Semidefinite Programming (SDP) approaches are more or less the only promising tools we have to prove that such problems are tractable and, while we wait for NP-hardness result (for now, we only have “Unique-Games-hardness”), it is good to see whether certain candidate LP and SDP algorithms have any chance, or if they admit counterexamples showing large gaps between the optimum of the relaxation and the combinatorial optimum.

The problem with this approach is the nearly endless variety of relaxations that one can consider: what happens when we add triangle inequalities? and pentagonal inequalities? and so on. As in the case of Yannakakis’s result, it would be great to have a result that says “all SDP relaxations of Vertex Cover of type X fail to achieve an approximation ratio smaller than 2,” where “type X” is a general class of sub-exponential size SDP relaxations that include the type of inequalities that people use “in practice.”

Lovasz and Schrijver describe a method, denoted LS+, that starts from an LP relaxation of a problem (actually it can start from any convex relaxation), and then turns it into tighter and tighter SDP relaxations, by adding auxiliary variables and linear and semidefinite constraints. A weaker version of the method, denoted LS, only adds auxiliary variables and linear constraints.

A nice thing about the method is that, after you apply it to your initial relaxation, thus getting a tighter relaxation, you can then apply it again to the tighter one, thus getting an even better relaxation, and so on. Starting from an LP relaxation with $n$ variables and poly( $n$ ) constraints, $k$ applications of the method yield a relaxation solvable in $n^{O(k)}$ time, which is polynomial for all fixed $k$ and sub-exponential for $k=o(n/log n)$ . Lovasz and Schrijver prove that, after $k$ applications (or “rounds”) the resulting relaxation enforces all inequalities over $k$ -tuples of variables that are valid for 0/1 solutions. (In particular, one gets the combinatorial optimum after $n$ rounds.) Typical approaches in the design of approximation algorithms are SDP with local inequalities (triangle inequalities etc.), and this is all captured after a few rounds of LS+.

It would be great to show that no constant (ideally, no sublinear) number of rounds of LS+ starting from the basic LP relaxation gives a $2-\epsilon$ approximation for vertex cover. Arora, ~~and others~~ Bollobas and Lovasz considered related questions in a FOCS 2002 paper that has inspired a considerable amount of later work. (See the introduction of the journal version.) Unfortunately the question remains open evern for two rounds of LS+. After one round, one gets an SDP relaxation equivalent to (number of vertices minus) the Lovasz Theta function, and Goemans and Kleinberg prove that such SDP does not achieve approximation better than 2. Beyond that, it is pretty much terra incognita. Charikar proves that a relaxation with triangle inequalities (which is incomparable with two rounds of LS+ and is weaker than three rounds) does not achieve approximation better than 2. Also, a sublinear number of rounds of LS+ does not achieve approximation better than 7/6. For LS, which, I remind you, generates linear programming relaxations rather than semidefinite programming ones, we know that no sublinear number of rounds leads to an approximation better than 2.

I will illustrate the main idea in the LS and LS+ method using the example of Vertex Cover. In the linear programming formulation, we have variables $x_i$ , one for each vertex $i$ , and the constraints that $x_i + x_j \geq 1$ for each edge $(i,j)$ and that $0\leq x_i \leq 1$ . We would like to add constraints that are only satisfied by 0/1 solutions, and the constraint $x_i^2 = x_i$ would work beautifully except that it is not linear (nor convex). Instead, Lovasz and Schrijver add new variables $y_{i,j}$ , one for each pair of vertices, with the idea that we would like to have $y_{i,j}=x_i * x_j$ ; then they add the requirement $y_{i,i} = x_i$ and various inequalities that make the $y_{i,j}$ be “sort of like” $x_i*x_j$ . In particular, we would like to require that if $x_k \neq 0$ , then $x_i = y_{i,k}/x_k$ . This is again a non-linear constraint, but, at least, we can check whether, for each fixed $k$ , $y_{i,k}/x_k$ is a fractional vertex cover: we just need to check the inequalities $y_{i,k} + y_{j,k} \geq x_k$ for each edge $(i,j)$

Similarly, if $x_k \neq 1$ , we expect to have $x_i = (x_i-y_{i,k})/(1-x_k)$ . We cannot check it directly, but we can check if
$x_i - y_{i,k} + x_j - y_{j,k} \geq 1-x_k$
hold for each edge $(i,j)$ . Finally, we obviously want $y_{i,j} = y_{j,i}$ . This describe the LS method. For LS+, we add the requirement that the symmetric matrix $(y_{i,j})$ be positive semidefinite. Being positive semidefinite means that there are vectors $b_1,\ldots,b_n$ such that
$y_{i,j} = \langle b_i,b_j \rangle$
where $\langle \cdot , \cdot \rangle$ denotes inner product. If $y_{i,j} = x_i *x_j$ then $(y_{i,j})$ is clearly positive semidefinite.