<p>Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H_n$ greedy algorithm does not readily extend to the set <em>partial cover</em> problem, where the goal is to pick a minimum-cost family of sets to cover $p \cdot n$ of the $n$ elements, where $0&lt;p&lt;1$ is a constant. But it sure seems to!</p>

<p>Greedy: repeatedly choose the most cost-effective set, i.e., one minimizing $c(S)  /\min(|S-C|,pn-|C|)$, where $C$ is the set of elements covered so far.</p>

<p>That is, the standard set cover greedy's cost-effectiveness definition is modified so that the benefit of a set is the min of # new elements and # of additional elements you still need to get.</p>

<p>Then <em>it would seem</em> that you can just say: number the elements $e_1,...,e_{pn}$ in order covered (ignoring any additional ones covered--we'll allocate all the costs to these first $pn$ elements), and argue that at the moment when greedy covers $e_k$, choosing all of $OPT$ would take care of your outstanding $\ge pn-k+1$ element needs, with cost per "satisfied element need" of at most $\alpha = OPT/(pn-k+1)$, so there's got to be a set that's at least that good, so greedy's going to choose one at least that good, which gives us a total bound of $OPT \sum_{i=1}^{pn} 1/(pn-k+1) = H_{pn} OPT$.</p>

<p>But apparently this argument is flawed. How so?</p>

<p>(Slivak writes in his thesis, "Even though [the algorithms] are quite similar, it turns out that the approach used by Chvatal, Lovasz, or Johnson cannot be used to establish a reasonable bound on the performance [...]. The reasons are that only a fraction of points of the set $U$ are covered and that the part of $U$ covered by the optimum partial cover can be completely different from the part covered by the greedy cover. This makes the analysis of the performance bound [...] quite complicated."
<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.5734&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.5734&amp;rep=rep1&amp;type=pdf</a> And Kearns proved a $2H_n+3$ bound, and presumably not because he simply overlooked the obvious approach.)</p>

CC BY-SA 3.0
2014-02-13T00:52:37.313Z
Thanks @NealYoung, I guess that--the $H_d$ guarantee, not the $H_{pn}$--must have been what Slavik (and everyone paraphrasing him) had in mind.
Matt
CC BY-SA 3.0
2014-02-11T03:30:00.253Z
Wolsey gave a generalization of set cover: "minimizing a linear function subject to a submodular constraint" [reference](http://greedyalgs.info/blog/appendix-standard/set-cover-wolsey/). Partial cover is (I think?) a special case: "choose a collection $S$ of sets of minimum total cost s.t. $f(S) \ge p\cdot n$."  Where $$f(S) = \min\Big(p\cdot n, \big|\cup_{s\in S} s\big|\Big)$$ is the size of the union of the sets in $S$, or your $p\cdot n$, whichever is less.  For integer-valued submodular functions $f$ such as this, his bound is $H_k$, where $$k=\max_s f(\{s\})-f(\{\}) \le n.$$  .
Neal Young
CC BY-SA 3.0
2014-02-11T04:38:46.483Z
Thanks Neal, I know the result is *true*, what I don't understand is why the simple adaptation of the classical argument I rehearse above is *invalid*, as several authors have stated.

E.g., Elomaa & Kujala (http://www.cs.uleth.ca/~benkoczi/files/papers/psetcover-2010.pdf) also write, "The straightforward analysis of the greedy method for Partial Cover becomes quite complicated because the optimal solution may cover a different set than those chosen by the greedy algorithm. Thus, the methods used by Johnson, Lovasz, and Chvatal ...do not directly generalize..."

Where does it actually break?
Matt
CC BY-SA 3.0
2014-02-11T15:35:44.817Z
The "standard" analysis of set cover via the LP relaxation is messy to generalize to partial cover because the LP relaxation for partial cover is not as clean as that for the standard set cover problem. What is the primal and dual you are referring to when you talk about the allocation of costs?
Chandra Chekuri
CC BY-SA 3.0
2014-02-11T19:15:23.450Z
@Chandra I'm not referring to any primal/dual at all here, just naively adapting the direct analysis (as in e.g. ch.2 of the Vazirani text), i.e., just charging equal shares of $c(S)$ for each chosen $S$ to the helpful elements that $S$ gives us, and then bounding and summing up those charge values.   I'm not able to find the bug in that analysis.
Matt
CC BY-SA 3.0
2014-02-11T19:37:04.290Z
@Chandra-Chekuri By the way, this is given as Exercise 1.1.b in the Williamson & Shmoys text, and, unlike the other research-level exercises, there oddly is no reference to the literature, which I'd (wrongly?) taken as an indication that a standard argument would suffice.
Matt
CC BY-SA 3.0
2014-02-12T04:12:38.390Z
Ok, I think I see the flaw. Suppose you need to cover only 1 element but Greedy picks a set with cost C that covers all the elements because its density C/n is small. On the other hand the optimal value is to cover a single element with a set of cost 1. Clearly Greedy is far from optimal. The way you are You cannot pay for the last set picked by Greedy by only the few remaining elements that need to reach the threshold pn.
Chandra Chekuri
CC BY-SA 3.0
2014-02-12T05:39:26.500Z
@ChandraChekuri No, this issue is handled by the slightly modified definition of cost effectiveness: $c(S)/min(|S−C|,pn−|C|)$ (i.e., cost over # of "helpful" new elements). In your example, $pn-|C|=1$, so the large set has bad cost effectiveness.  Remember, the $H_{pn}$ approx *result* is actually true (and proven by Slivak); it's just the simple argument above for this result that's supposed to be flawed somehow.
Matt
CC BY-SA 3.0
2014-02-12T06:13:04.903Z
Ok, I see, thanks. We know greedy works in an even more general setting due to Wolsey's result. I have not seen the comments of Slavik etal so hard to tell why they say so.
Chandra Chekuri
CC BY-SA 3.0
2014-02-12T09:27:19.027Z
Matt, rereading more carefully, I don't see any flaw in your proof.  However, the standard greedy set-cover analysis proves the tighter ratio of $H_d$ where $d$ is the maximum set size.  (The argument there is that you can charge all of greedy's cost to the elements so that each set $S$ in OPT is charged at most $H_{|S|}c_S$.)  For partial cover, the $H_d$ bound holds too, but I don't see how your argument extends to give it, as you would be charging greedy's cost to elts that OPT might not cover.  This wouldn't explain why Kearns settled for $2H_n+3$ though.
Neal Young
<ds.algorithms><approximation-algorithms><set-cover>
Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?
Matt
# Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?

(Asked by: username_0 on 2014-02-10)

Several authors, starting with Slavik, have noted that the classical analysis of the set cover $H\_n$ greedy algorithm does not readily extend to the set *partial cover* problem, where the goal is to pick a minimum-cost family of sets to cover $p \cdot n$ of the $n$ elements, where $0

Greedy: repeatedly choose the most cost-effective set, i.e., one minimizing $c(S) /\min(|S-C|,pn-|C|)$, where $C$ is the set of elements covered so far.

That is, the standard set cover greedy's cost-effectiveness definition is modified so that the benefit of a set is the min of # new elements and # of additional elements you still need to get.

Then *it would seem* that you can just say: number the elements $e\_1,...,e\_{pn}$ in order covered (ignoring any additional ones covered--we'll allocate all the costs to these first $pn$ elements), and argue that at the moment when greedy covers $e\_k$, choosing all of $OPT$ would take care of your outstanding $\ge pn-k+1$ element needs, with cost per "satisfied element need" of at most $\alpha = OPT/(pn-k+1)$, so there's got to be a set that's at least that good, so greedy's going to choose one at least that good, which gives us a total bound of $OPT \sum\_{i=1}^{pn} 1/(pn-k+1) = H\_{pn} OPT$.

But apparently this argument is flawed. How so?

(Slivak writes in his thesis, "Even though [the algorithms] are quite similar, it turns out that the approach used by Chvatal, Lovasz, or Johnson cannot be used to establish a reasonable bound on the performance [...]. The reasons are that only a fraction of points of the set $U$ are covered and that the part of $U$ covered by the optimum partial cover can be completely different from the part covered by the greedy cover. This makes the analysis of the performance bound [...] quite complicated."
<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.5734&rep=rep1&type=pdf> And Kearns proved a $2H\_n+3$ bound, and presumably not because he simply overlooked the obvious approach.)

**Tags:** ds.algorithms, approximation-algorithms, set-cover

> **Comments:**
> **username_1**: Wolsey gave a generalization of set cover: "minimizing a linear function subject to a submodular constraint" [reference](http://greedyalgs.info/blog/appendix-standard/set-cover-wolsey/). Partial cover is (I think?) a special case: "choose a collection $S$ of sets of minimum total cost s.t. $f(S) \ge p\cdot n$."  Where $$f(S) = \min\Big(p\cdot n, \big|\cup_{s\in S} s\big|\Big)$$ is the size of the union of the sets in $S$, or your $p\cdot n$, whichever is less.  For integer-valued submodular functions $f$ such as this, his bound is $H_k$, where $$k=\max_s f(\{s\})-f(\{\}) \le n.$$  .  
> **username_0**: Thanks Neal, I know the result is *true*, what I don't understand is why the simple adaptation of the classical argument I rehearse above is *invalid*, as several authors have stated.  E.g., Elomaa & Kujala (http://www.cs.uleth.ca/~benkoczi/files/papers/psetcover-2010.pdf) also write, "The straightforward analysis of the greedy method for Partial Cover becomes quite complicated because the optimal solution may cover a different set than those chosen by the greedy algorithm. Thus, the methods used by Johnson, Lovasz, and Chvatal ...do not directly generalize..."  Where does it actually break?  
> **username_2**: The "standard" analysis of set cover via the LP relaxation is messy to generalize to partial cover because the LP relaxation for partial cover is not as clean as that for the standard set cover problem. What is the primal and dual you are referring to when you talk about the allocation of costs?  
> **username_0**: @Chandra I'm not referring to any primal/dual at all here, just naively adapting the direct analysis (as in e.g. ch.2 of the Vazirani text), i.e., just charging equal shares of $c(S)$ for each chosen $S$ to the helpful elements that $S$ gives us, and then bounding and summing up those charge values.   I'm not able to find the bug in that analysis.  
> **username_0**: @Chandra-Chekuri By the way, this is given as Exercise 1.1.b in the Williamson & Shmoys text, and, unlike the other research-level exercises, there oddly is no reference to the literature, which I'd (wrongly?) taken as an indication that a standard argument would suffice.  
> **username_2**: Ok, I think I see the flaw. Suppose you need to cover only 1 element but Greedy picks a set with cost C that covers all the elements because its density C/n is small. On the other hand the optimal value is to cover a single element with a set of cost 1. Clearly Greedy is far from optimal. The way you are You cannot pay for the last set picked by Greedy by only the few remaining elements that need to reach the threshold pn.  
> **username_0**: @ChandraChekuri No, this issue is handled by the slightly modified definition of cost effectiveness: $c(S)/min(|S−C|,pn−|C|)$ (i.e., cost over # of "helpful" new elements). In your example, $pn-|C|=1$, so the large set has bad cost effectiveness.  Remember, the $H_{pn}$ approx *result* is actually true (and proven by Slivak); it's just the simple argument above for this result that's supposed to be flawed somehow.  
> **username_2**: Ok, I see, thanks. We know greedy works in an even more general setting due to Wolsey's result. I have not seen the comments of Slavik etal so hard to tell why they say so.  
> **username_1**: username_0, rereading more carefully, I don't see any flaw in your proof.  However, the standard greedy set-cover analysis proves the tighter ratio of $H_d$ where $d$ is the maximum set size.  (The argument there is that you can charge all of greedy's cost to the elements so that each set $S$ in OPT is charged at most $H_{|S|}c_S$.)  For partial cover, the $H_d$ bound holds too, but I don't see how your argument extends to give it, as you would be charging greedy's cost to elts that OPT might not cover.  This wouldn't explain why Kearns settled for $2H_n+3$ though.  
> **username_0**: Thanks @NealYoung, I guess that--the $H_d$ guarantee, not the $H_{pn}$--must have been what Slavik (and everyone paraphrasing him) had in mind.  

---

## 0 answers

