Thursday, January 17, 2008

Max-Coverage vs. Min-Set-Cover

A quick note to say that these problems are very closely related. Set-Cover is of course more famous, but in quite a few cases the analysis and understanding of Max-Coverage is simpler. In the lectures I'll actually switch between them to make my points.

Formally, there's a straightforward reduction from Min-Set-Cover to Max-Coverage. (A reduction in the opposite direction is not obvious to me: can anybody think of one?) I was going to make this a homework problem but then I forgot.

Specifically:

Proposition: Suppose there is a 1 vs. 1 - $\gamma$ search algorithm for Max-Coverage. Then there is a $\lceil \log_{(1/\gamma)}$ $n \rceil$ factor search algorithm for Min-Set-Cover.

Remark: So if we got our 1 vs. 1 - 1/e algorithm for Max-Coverage via Greedy and somehow failed to notice the ln n algorithm for Min-Set-Cover, this reduction would give it. Additionally, if we prove ln n hardness for Min-Set-Cover, this reduction automatically gives 1 vs. 1 - 1/e hardness for the search version of Max-Coverage. Unfortunately, it's a little easier to prove hardness for Max-Coverage, and that's what we'll see in next Tuesday's class. (To compensate a tiny bit, we'll at least prove the 1 vs. 1 - 1/e decision version of Max-Coverage is hard.)

Proof: Suppose we have a Min-Set-Cover instance with optimum Opt. Since 1 $\leq$ Opt $\leq n$, we can "guess" Opt's value in polynomial time. [Exercise: at the end of the proof, explain this rigorously.] Now run the 1 vs. 1 - $\gamma$ search algorithm for Max-Coverage with "m" = Opt. By assumption, this Max-Coverage instance has value 1, so we will get a collection of Opt sets which leave less than a $\gamma$ fraction of ground elements uncovered.

"Delete" all the covered elements from the instance, simplifying it. Now there are still (at most) Opt sets which cover all the uncovered elements. So we can run the Max-Coverage instance again and get Opt more sets which reduce the fraction of uncovereds down to $\gamma^2$.

Ergo etc., as they used to say. If we do $t$ iterations of this we will have chosen $t \cdot$ Opt sets and we can stop once $\gamma^t \lt 1/n$; i.e., $t \gt \log_{(1/\gamma)}$ $n$.

4 comments:

jblocki said...

By "guessing the value for Opt" we mean run binary search using the search algorithm, correct?

Ryan O'Donnell said...

Not exactly... we have a search algorithm for Max-Coverage but we are talking about the Min-Set-Cover Opt here...

Anonymous said...

We don't need to find OPT. One can run the search algorithm for increasing values of m, till the first time you cover (1-\gamma) fraction of elements. This m will be at most OPT. Just remove the elements covered, and repeat the above...

Ryan O'Donnell said...

Anon: Good point.

(I was thinking of the more generic reduction of trying all possible values for Opt, and then in the very end, using the best solution found. On the instance where you were using the right Opt, you'll get a good solution, so the overall best will be at least as good. But your solution is better in this case.)