2
$\begingroup$

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<p<1$ is a constant. But it sure seems to!

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.)

Improve this question
$\endgroup$
10
  • $\begingroup$ Wolsey gave a generalization of set cover: "minimizing a linear function subject to a submodular constraint" reference. 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.$$ . $\endgroup$
    – Neal Young
    Commented Feb 11, 2014 at 3:30
  • $\begingroup$ 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 (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? $\endgroup$
    – Matt
    Commented Feb 11, 2014 at 4:38
  • 1
    $\begingroup$ 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? $\endgroup$
    – Chandra Chekuri
    Commented Feb 11, 2014 at 15:35
  • $\begingroup$ @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. $\endgroup$
    – Matt
    Commented Feb 11, 2014 at 19:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Feb 12, 2014 at 9:27

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.