Notes of Ryan O’Donnell’s lecture nr 2


1. Hardness of MAX {k}-COVER


1.1. The Theorem


Today, I explain the proof of Feige’s theorem, hardness of approximation of MAX {k}-COVER. It relies on NP-hardness of {(1,\delta)}-approximating MAX PROJECTION{(L,R)} (also known as LABEL COVER) for all {\delta}, a result due to Ran Raz and following from PCP and parallel repetition.

Recall that this problem has

  • input : a regular bipartite graph, and for each edge, a projection constraint : {\pi_{uv}:[L]\rightarrow[R]}.
  • output: an assigment of labels in {[L]} and {[R]} to vertices.
  • objective: fraction of constraints satisfied.

Feige’s precise theorem is

Theorem 1 There is a Karp reduction of {(1,\delta^3 /1000)}-approximating MAX PROJECTION{(L,R)} to {(1,1-e^{-1}+\delta)}-approximating MAX {k}-COVER.


1.2. The proof


The reduction uses the following gadget. Let {\Omega=\{ 0,1 \}^{R}}, {k=2}, sets

\displaystyle  \begin{array}{rcl}  S_{j}^{b}=\{x\in\{ 0,1 \}^R \,;\,x_j =b\}. \end{array}

The {OPT} of this instance is {1}. Indeed, two sets suffice to cover {\Omega}. But only the obvious pairs achieve this. Every other pair has value {\leq 3/4}.

Also, even a cheating solution taking a bounded number of sets does poorly if it is inconsistent. Consistent here means that covering includes a pair {\{S_{j}^{0},S_{j}^{1}\}}. Inconsistent solutions achieve at most {1-2^{-?}}.

Proof: Start with a MAX PROJECTION instance {U}, {V}, {\pi_{uv}}. We put a copy of the gadget on top of each edge. For {e\in E}, there is a ground set {\Omega_e}, a copy of {\{ 0,1 \}^R}. Overall {\Omega=\bigcup_{e}\Omega_{e}}. For each vertex {v\in V}, define sets {S_{1}^{v},\ldots,S_{R}^{v}} to be the {S_{j}^{1}}‘s. For {u'\sim v}, the sets {S_{j}^{v}} cover {\Omega_{u'v}}. For {v'\sim u}, the {S_{i}^{u}}‘s cover {\{x\in\Omega_{uv'}\,;\,x_{\pi_{uv}(i)}=0}.

Note that {\Omega_{uv}} can be covered only by pairs {\{S_{j}^{v},S_{j}^{u}\}}.

Let {k=|U|+|V|}. Let us prove completeness: if there is an assignment {\alpha} satisfying {1}-fraction of MAX PROJECTION constraints, then there exist {k} sets covering {\Omega}. Indeed, consider all the {S_{\alpha(w)}^{w}} for {w\in U\cup V}. It covers {\Omega_{uv}} since it contains {S_{j}^{1}} and covers {S_{j}^{0}} with {j=\pi_{uv}(\alpha(u))=\alpha(v)}.

Soundness means that if best assignment {\alpha} satisfies {<\delta^3 /1000} of constraints, then any {k} sets cover at most {\frac{3}{4}+\delta} fraction of {\Omega}. By contrapositive. Assume {OPT} of covering is {>\frac{3}{4}+\delta}, i.e. there is a collection {\mathcal{S}} of {k} sets with coverage {>\frac{3}{4}+\delta}. We shall decode {\mathcal{S}} into an assignement {\alpha:U\rightarrow[L]}, {V\rightarrow[R]} satsfying {\geq \delta^3 /1000} of {\pi_{uv}} constraints.

We do not need to be clever to achieve {3/4}. Here is some terminology.

Definition 2 For {v\in V}, let {suggest(v)=\{j\in[R]\,;\, S_{j}^{v}\in\mathcal{S}\}} and for {u\in U}, {suggest(u)=\{i\in[L]\,;\, S_{i}^{u}\in\mathcal{S}\}}. Then define

\displaystyle  \begin{array}{rcl}  Sets(u,v)=\textrm{ list of all } S_{i}^{u},\, S_{j}^{v}\in\mathcal{S}. \end{array}

{Sets(u,v)} is consistent in above sens iff {\exists i\in suggest(u)}, {\exists j\in suggest(v)} such that {j=\pi_{uv}(i)}. Since {|Sets(u,v)|=|suggest(u)|+|suggest(v)|=k}, we have {|suggest(v)|=1} in average. {|U|=|V|} and regularity implies that {|Sets(u,v)|=2} on average over edges. Now we are ready to decode, i.e. make an assignment {\alpha} by picking for {\alpha(w)} a random element of {suggest(w)}, unless it is empty, in which case pick it arbitrarily. There remains to estimate the score of {\alpha}, which do not do here. Note that {\delta^3 /1000} is not greedy. \Box


1.3. What should we remember from this proof


To prove {(c,s+\delta)}-inapproximability for MAX BLAH, it suffices to reduce from MAX PROJECTION using a gadget (instance of MAX BLAH) with special properties.

  1. Sets involved are cubes {\{ 0,1 \}^R}.
  2. {OPT} of gadget is {c}. Further, there exist exactly {R} optimal solutions corresponding to hald-cubes {\{x_i =1\}}.
  3. Every solution of the gadget should suggest at most a constant number of optimal solutions.
  4. Solution which suggest no optimal solutions should have value {\leq s + O_{\delta}(1)}.

Theorem 3 This methodology of gadgets is a theorem, but only if you reduce from MAX BIJECTION.


Definition 4 MAX BIJECTION is MAX PROJECTION where {\pi_{uv}}‘s are bijections.


Unfortunately, MAX BIJECTION is not a hard problem. Indeed, {(1,1)}-approximating MAX BIJECTION{(R)} is in P.

Subhash Khot’s Unique Games Conjecture states that {\forall \delta>0}, {\exists R} such that MAX BIJECTION{(R)} is {(1-\delta,\delta)}-inapproximable.

Then, above technology implies

Theorem 5 Assuming UGC, inapproximability results can be obtained for many problems in a routine manner.

The point is wether the method allows to get tight inapproximability bounds. Answer is yes for certain problems, but it requires sometimes a highly non trivial and mathematical analysis of the various gadget properties above, especially the last one.





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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s