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.)
Why doesn't the standard analysis of set cover $H_n$ greedy extend to partial cover?
ds.algorithms;approximation algorithms;set cover