1. Hardness of MAX -COVER
1.1. The Theorem
Today, I explain the proof of Feige’s theorem, hardness of approximation of MAX -COVER. It relies on NP-hardness of -approximating MAX PROJECTION (also known as LABEL COVER) for all , 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 : .
- output: an assigment of labels in and to vertices.
- objective: fraction of constraints satisfied.
Feige’s precise theorem is
Theorem 1 There is a Karp reduction of -approximating MAX PROJECTION to -approximating MAX -COVER.
1.2. The proof
The reduction uses the following gadget. Let , , sets
The of this instance is . Indeed, two sets suffice to cover . But only the obvious pairs achieve this. Every other pair has value .
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 . Inconsistent solutions achieve at most .
Proof: Start with a MAX PROJECTION instance , , . We put a copy of the gadget on top of each edge. For , there is a ground set , a copy of . Overall . For each vertex , define sets to be the ‘s. For , the sets cover . For , the ‘s cover .
Note that can be covered only by pairs .
Let . Let us prove completeness: if there is an assignment satisfying -fraction of MAX PROJECTION constraints, then there exist sets covering . Indeed, consider all the for . It covers since it contains and covers with .
Soundness means that if best assignment satisfies of constraints, then any sets cover at most fraction of . By contrapositive. Assume of covering is , i.e. there is a collection of sets with coverage . We shall decode into an assignement , satsfying of constraints.
We do not need to be clever to achieve . Here is some terminology.
Definition 2 For , let and for , . Then define
is consistent in above sens iff , such that . Since , we have in average. and regularity implies that on average over edges. Now we are ready to decode, i.e. make an assignment by picking for a random element of , unless it is empty, in which case pick it arbitrarily. There remains to estimate the score of , which do not do here. Note that is not greedy.
1.3. What should we remember from this proof
To prove -inapproximability for MAX BLAH, it suffices to reduce from MAX PROJECTION using a gadget (instance of MAX BLAH) with special properties.
- Sets involved are cubes .
- of gadget is . Further, there exist exactly optimal solutions corresponding to hald-cubes .
- Every solution of the gadget should suggest at most a constant number of optimal solutions.
- Solution which suggest no optimal solutions should have value .
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 ‘s are bijections.
Unfortunately, MAX BIJECTION is not a hard problem. Indeed, -approximating MAX BIJECTION is in P.
Subhash Khot’s Unique Games Conjecture states that , such that MAX BIJECTION is -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.