Notes of Konstantinos Georgiou’s talk, jan. 20

Fooling strong LP and SDP relaxations for VERTEX COVER

Scribes: Pierre Pansu and Claire Mathieu

The problem: VERTEX COVER

  • Input: a graph.
  • Output: a set of vertices touching all edges.
  • Objective: minimize size

Dinur Safra: {1.36}-inapproximable assuming P{\not=}NP.
KR: {2-o(1)}-inapproximable assuming UGC.

Typical approximation algorithms: solve a relaxation, round the solution to make it a true vertex cover. Typical analysis: compare the cost of the rounded solution to the cost fot the solution to the relaxation.

1. The standard linear programming (LP) relaxation

Exact formulation (Integer Program, intractable): {x_i} takes value {0} or {1}. Minimize {\sum_i x_i} under constraints {x_i +x_j \geq 1} for each edge {ij}.

Standard LP relaxation (Linear Program, polynomial-time solvable) consists in replacing “{x_i=0} or {1}” by {x_i \in[0,1]}.

Integrality gap is the maximum over all {n} vertex graphs of the ratio of the value of the IP over the value of the LP. For algorithms that first solve a relaxation, then round it to a solutino of the original problem, the analysis is always done by relating the value of the output to the value of the relaxation, and so, even if the rounding is wonderful, the proof shows that such an algorithm has an approximation ratio that, at best, equals the integrality gap. Hence the interest in evaluating integrality gaps.

The above LP relaxation has an integrality ratio of almost 2, in fact, of {\frac{n-1}{n/2}}, achieved by the {n}-vertex clique. This means that, using this LP to design an approximtion algorithm, no matter what the rounding, we cannot hope for an approximation ratio better than {2-o(1)}. We say that this LP relaxation is fooled by cliques. Goemans Kleinberg 1995.

2. The standard semi-definite programming (SDP) relaxation

If {x_0} encodes “belongs to vertex cover”, then for each vertex {i}, {x_i =x_0} or not. Exact formulation: Minimize {\frac{1}{4}\sum_i (x_i -x_0)^2} under constraints {|x_i|^2 =1} for all {i}, {|x_0|^2 = 1}, and, for all edges {ij},

\displaystyle  \begin{array}{rcl}  |x_0 -x_i|^2 +|x_0 -x_j|^2 \geq |x_j -x_i|^2 . \end{array}

Standrad SDP relaxation (semi-definite program, essentially polynomial-time solvable) consists in replacing numbers (one-dimensional vectors) {x_i}‘s by vectors (no constraints on dimensions — may have {n} dimensions).

This SDP relaxation is not fooled by cliques but the integrality gap is still {2-o(1)}. The integrality gap is reached for Frankl-Rödl graphs. These graphs are parametrized by {\gamma}. Vertices are {\{ 0,1 \}^m}, edges connect vertices at Hamming distance {(1-\gamma)m}. For {\gamma=0}, each vertex has exactly one edge, to the antipodal vertex, and we get a perfect matching, so there is a vertex cover of size {n/2}. For {\gamma=1} we get the complete graph, and the minimum vertex cover has size {n-1}. The Frankl-Rödl theorem says: fix {\gamma>0}. Then the minimum vertex cover has size {\geq n(1-o(1))}.

Can we lower the integrality gap by using other, stronger LP or SDP relaxations? That would give hope that there exists a better-than-2 approximation algorithm.

3. Stronger relaxations: {k}-gonal inequalities

Change the SDP relaxation by putting in additional inequalities (constraints). Use the metric induced by {|x_j -x_i|^2}. In an ideal world, vectors live in dimension {1} and integral solutions induce cut metrics, so if we add inequalities that are valid for cut metrics, it’s still a relaxation of the exact problem. For example, the {k}-gonal inequalities: take a set of vertices of odd size {k}, consisting of a subset {A} of size {k/2+1} and a subset *B* of size {k/2-1}: the inequality {\sum d(a,a') + \sum d(b,b') \leq \sum d(a,b)} is valid and can be added to the SDP relaxation. This creates a stronger SDP relaxation. What happens to the integrality gap?

Georgiou at al. 2009 : Even with {k}-gonal inequalities, the integrality gap is still {2-o(1)}. (Charikar 2002 had shown that for {3}-gonal inequalities). On what graph is the integrality gap reached? Still Frank-Rodl. How does the proof go? Given a polynomial {P} with positive coefficients, define {T_p : E\rightarrow} tensor algebra of {E}. Then {T_P (u)\cdot T_P (u)=P(u\cdot u)}. Applying this to the function {1-\frac{1}{2\pi}\arccos} gives a solution to the stronger SDP with value close to {n/2}.

4. Stronger relaxations: Lovasz-Schrijver, Sherali-Adams and Lasserre hierarchies

Level {t} Sherali-Adams applied to an LP relaxation produces a distribution on vertex covers which has the following property: it has one variable {x(S,b)} for each subset of at most {t} vertices and each assignment {b_1b_2...b_S} of 0s and 1s to the vertices of {S} ({b_i=1} means that vertex {i} is in the vertex cover). It has constraints expressing the fact that {(x(S,b))_b} is a distribution of vertex covers on the subgraph induced by {S}. It has constraitns expressing the fact that {(x(S,b))_b} abd {(x(S',b'))_b} must be consistent distributions, i.e. have the same marginal distribution over the intersection of {S} and {T}. When {t=2} this is the standard LP relaxation, when {t>2} this is a stronger LP relaxation (polynomial-time solvable for {t} bounded). What happens to the integrality gap? It’s still {2(1-o(1))} even for {t=n^\delta}. It is 1 for {t=n}.

What about combining the powers of Sherali-Adams and of SDPs? The standard SDP relaxation constrqints can be rewritten as: {y(i,i)=1} for all {i}, {y(0,0)=1}, {Y=(y(i,j))} positive semi-definite matrix, and, for all edges {ij},

\displaystyle  \begin{array}{rcl}  1-y(i,0)-y(j,0)\geq -y(i,j) . \end{array}

For consistency between the Sherali-Adams solution and the SDP solution we can add the constraint {y(i,i)=x_i}. That’s the “Sherali-Adams SDP version”. What happens to the integrality gap? For {t=3}, still {2-o(1)}. What graph provides the proof? Still the Frank-Rodl graph.

There are other hierarchies also depending on {t} (solvable in runtime exponential in {t}) and relations between them, comparing their relative strength in terms of reducing the integrality gap. None has a proved integrality gap less than {2(1_o(1))} except when {t} is at least {n^\delta}.



About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s