<p>Having discussed with other users, I believe the following answers the question. </p>

<p>To begin with let us recap the greedy algorithm for the set cover problem, in which we wish to cover all of $E$ as cheaply as possible. At each step, the algorithm adds the set $S_i$ for which $\frac{w_i}{|\hat{S}_i|}$ is lowest, where $\hat{S}_i$ is the subset of $S_i$ which has yet to be covered. It can be shown that this minimum is upper bounded by $\frac{OPT}{Z}$ where $OPT$ is the optimal weight for the (full) set cover problem and $Z$ is the number of elements not yet covered. From this, one can show a a total weight bounded by $H_{|E|} \approx \log |E|$. </p>

<p>However, if one were to stop the algorithm as soon as $p|E|$ elements were covered, then we would get the bound  $\approx \log \frac{1}{1-p}$, as per @SashoNikolov's comment.</p>

<p>We can get a $H_{p|E|}$ approximation for the partial set problem by modifying the greedy algorithm as follows: At each iteration, choose the $S_i$ which minimizes $\frac{w_i}{\min(|\hat{S}_i|, Z)}$ where $Z$ is the number of elements we still need to get to complete $p|E|$ elements. Now we can guaranteed that there is an $S_i$ for which the above is bounded by $OPT/Z$ (where now $OPT$ is the optimal for the partial set cover). To see this, suppose an optimal solution is the collection of sets $S_1=\{xx|...\}$ $S_2=\{xxx|...\}$, $S_3=\{xxx|......\}$. In this notation, the $x$ represents an already covered element, and after the $|$ are elements which are not covered. Let $a_1, a_2, a_3$ denote the number of such uncovered elements and suppose $a_1, a_2, a_3\leq Z$. Then 
$$min \{\frac{w_1}{a_1}, \frac{w_2}{a_2}, \frac{w_3}{a_3}\}\leq \frac{w_1+w_2+w_3}{a_1+a_2+a_3}  = \frac{OPT}{a_1+a_2+a_3} \leq \frac{OPT}{Z}.$$</p>

<p>Of course, if any of the $a_i$'s is larger than $Z$ then it is replaced by $Z$ in the above inequalities and they hold.</p>

<p>The starting $Z$ is $Z_0=p|E|$, and a similar analysis as for the full set cover leads to a total weight bounded by $OPT \cdot H_{Z_0}$.</p>

CC BY-SA 3.0
2016-04-17T00:04:59.507Z
FWIW I guess the latter algorithm is a special case of Wolsey's generalization of the greedy set-cover algorithm ([minimizing a linear function subject to a submodular constraint](http://scholar.google.com/scholar?q=author:%22L+Wolsey%22+intitle:%22+An+analysis+of+the+greedy+algorithm+for+the+submodular+set+covering+problem%22)).
Neal Young
CC BY-SA 3.0
2016-05-17T22:56:35.327Z
Wolsey's analysis proves a slightly stronger bound of $H_{d}$ where $d$ is the minimum of the maximum set size and $p|E|$.
Chandra Chekuri
CC BY-SA 3.0
2016-04-16T20:13:24.360Z
2016-04-16T20:13:24.360Z
John Harrison
<p>We have a set of elements $E=\{e_1, e_2, \ldots, e_m\}$, and $n$ subsets of $E$: $S_1, S_2, \ldots, S_n$ The union of those subsets is $E$, and each subset $S_i$ has a non-negative weight $w_i$. </p>

<p>The standard set cover problem is to find set of $S_i$'s whose union is $E$ and whose total weight is the smallest possible. </p>

<p>In the partial cover variation of this problem, we are given a $p \in (0,1)$ and are asked to find a minimum total cost set of $S_i$'s whose union has at least $p|E|$ elements.That is, find and index set $I \subseteq \{1,\ldots,n\}$ such that $|\bigcup_{i \in I}S_i| \geq p|E| $ and this is the cheapest set of $S_i$'s which have this property.</p>

<p>Give a polynomial time algorithm which finds a set of $S_i$'s whose union has at least $p|E|$ elements and whose total cost is at most $c(p)OPT$ where $OPT$ is the optimal cost of the set cover problem and $c(p)$ is a constant that depends on $p$. </p>

<p>My initial thought was that you could solve the relaxed version of the set cover problem, and do a rounding of the variables, where you round a variable $x_i$ (being associated with set $S_i$) to $1$ if $x_i \geq 1-p$, and otherwise round it down. This means the cost will be multiplied by a factor of no more than $1/(1-p)$.</p>

<p>The problem with this is that an element may be in many sets $S_i$ and so it may be the case that no $x_i &gt; 1-p$ for the constraint corresponding to this element.</p>

CC BY-SA 3.0
2016-04-15T15:36:09.483Z
If I am not mistaken, this is not possible: For the general set cover problem we know that there exists no approximation algorithm with factor better than $O(log n)$, unless P = NP. Now assume that we have an algorithm with the properties you require. Then when getting an instance of general set cover, we can add an element $e_{m+1}$ to $E$ and a set $S_{n+1} = \{ e_{m+1} \}$ to the set system; $S_{n+1}$ costs as much as all the other sets together. Now we run your algorithm with $p = n/(n+1)$. Then your algorithm will give us a constant factor approximation of set cover. Contradiction.
tranisstor
CC BY-SA 3.0
2016-04-15T20:43:02.193Z
$p$ is a constant, for argument's sake, we can just fix it to be, say, $0.9$. I think and argument like yours can be applied though. This is a text book exercise, I assumed it would be solvable, but perhaps it is not.
John Harrison
CC BY-SA 3.0
2016-04-16T03:14:32.143Z
It is solvable, and @tranisstor's example is not an issue. hint: the approximation factor is $O(\log(1/(1-p)))$.
Sasho Nikolov
CC BY-SA 3.0
2016-04-16T12:11:08.417Z
You mean do the greedy algorithm for the set cover problem until you have less than (1-p)m elements  left?
John Harrison
CC BY-SA 3.0
2016-04-16T17:57:50.823Z
By "$OPT$ is the optimal cost of the set-cover problem", do you mean the minimum cost to cover *all* elements, or the minimum cost to cover $p|E|$ elements?  If it's the former (as assumed by @SashoNikolov), the greedy algorithm gives a constant-factor approximation (you can show this following one of the standard analyses of greedy for set cover).  If it's the latter (as assumed by @tranisstor), the greedy algorithm gives a $H_{|E|} \approx \ln |E|$ approximation, which is essentially best possible as the problem is as hard as set cover.
Neal Young
CC BY-SA 3.0
2016-04-16T19:06:17.353Z
@NealYoung I meant to cover all the elements, and after Sasho's  hint, realized the greedy does give the approximation factor he mentioned. I believe that you can generalize this algorithm for the partial cover problem to give a $H_{p|E|}$ approximation factor. The algorithm divides the weight by the number of elements in the set, or by the number you need to get to have $p|E|$, whichever is smaller. A similar analysis as for the full cover case gives the a weight bounded by $H_{p|E|}OPT$, where this time $OPT$ is the optimal for the partial cover.
John Harrison
CC BY-SA 3.0
2016-06-16T10:10:26.250Z
Isn't it the result of Feige for max k-set cover where the 0.632 approximation is shown to be essentially tight? http://dl.acm.org/citation.cfm?id=285059
Olf
<approximation-algorithms><set-cover>
Partial cover approximation
John Harrison
# Partial cover approximation

(Asked by: username_0 on 2016-04-15)

We have a set of elements $E=\{e\_1, e\_2, \ldots, e\_m\}$, and $n$ subsets of $E$: $S\_1, S\_2, \ldots, S\_n$ The union of those subsets is $E$, and each subset $S\_i$ has a non-negative weight $w\_i$.

The standard set cover problem is to find set of $S\_i$'s whose union is $E$ and whose total weight is the smallest possible.

In the partial cover variation of this problem, we are given a $p \in (0,1)$ and are asked to find a minimum total cost set of $S\_i$'s whose union has at least $p|E|$ elements.That is, find and index set $I \subseteq \{1,\ldots,n\}$ such that $|\bigcup\_{i \in I}S\_i| \geq p|E| $ and this is the cheapest set of $S\_i$'s which have this property.

Give a polynomial time algorithm which finds a set of $S\_i$'s whose union has at least $p|E|$ elements and whose total cost is at most $c(p)OPT$ where $OPT$ is the optimal cost of the set cover problem and $c(p)$ is a constant that depends on $p$.

My initial thought was that you could solve the relaxed version of the set cover problem, and do a rounding of the variables, where you round a variable $x\_i$ (being associated with set $S\_i$) to $1$ if $x\_i \geq 1-p$, and otherwise round it down. This means the cost will be multiplied by a factor of no more than $1/(1-p)$.

The problem with this is that an element may be in many sets $S\_i$ and so it may be the case that no $x\_i > 1-p$ for the constraint corresponding to this element.

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

> **Comments:**
> **username_1**: If I am not mistaken, this is not possible: For the general set cover problem we know that there exists no approximation algorithm with factor better than $O(log n)$, unless P = NP. Now assume that we have an algorithm with the properties you require. Then when getting an instance of general set cover, we can add an element $e_{m+1}$ to $E$ and a set $S_{n+1} = \{ e_{m+1} \}$ to the set system; $S_{n+1}$ costs as much as all the other sets together. Now we run your algorithm with $p = n/(n+1)$. Then your algorithm will give us a constant factor approximation of set cover. Contradiction.  
> **username_0**: $p$ is a constant, for argument's sake, we can just fix it to be, say, $0.9$. I think and argument like yours can be applied though. This is a text book exercise, I assumed it would be solvable, but perhaps it is not.  
> **username_2**: It is solvable, and @username_1's example is not an issue. hint: the approximation factor is $O(\log(1/(1-p)))$.  
> **username_0**: You mean do the greedy algorithm for the set cover problem until you have less than (1-p)m elements  left?  
> **username_3**: By "$OPT$ is the optimal cost of the set-cover problem", do you mean the minimum cost to cover *all* elements, or the minimum cost to cover $p|E|$ elements?  If it's the former (as assumed by @SashoNikolov), the greedy algorithm gives a constant-factor approximation (you can show this following one of the standard analyses of greedy for set cover).  If it's the latter (as assumed by @username_1), the greedy algorithm gives a $H_{|E|} \approx \ln |E|$ approximation, which is essentially best possible as the problem is as hard as set cover.  
> **username_0**: @NealYoung I meant to cover all the elements, and after Sasho's  hint, realized the greedy does give the approximation factor he mentioned. I believe that you can generalize this algorithm for the partial cover problem to give a $H_{p|E|}$ approximation factor. The algorithm divides the weight by the number of elements in the set, or by the number you need to get to have $p|E|$, whichever is smaller. A similar analysis as for the full cover case gives the a weight bounded by $H_{p|E|}OPT$, where this time $OPT$ is the optimal for the partial cover.  
> **username_4**: Isn't it the result of Feige for max k-set cover where the 0.632 approximation is shown to be essentially tight? http://dl.acm.org/citation.cfm?id=285059  

---

## 1 answers

### Answer by username_0 on 2016-04-16. Score: 1

Having discussed with other users, I believe the following answers the question.

To begin with let us recap the greedy algorithm for the set cover problem, in which we wish to cover all of $E$ as cheaply as possible. At each step, the algorithm adds the set $S\_i$ for which $\frac{w\_i}{|\hat{S}\_i|}$ is lowest, where $\hat{S}\_i$ is the subset of $S\_i$ which has yet to be covered. It can be shown that this minimum is upper bounded by $\frac{OPT}{Z}$ where $OPT$ is the optimal weight for the (full) set cover problem and $Z$ is the number of elements not yet covered. From this, one can show a a total weight bounded by $H\_{|E|} \approx \log |E|$.

However, if one were to stop the algorithm as soon as $p|E|$ elements were covered, then we would get the bound $\approx \log \frac{1}{1-p}$, as per @SashoNikolov's comment.

We can get a $H\_{p|E|}$ approximation for the partial set problem by modifying the greedy algorithm as follows: At each iteration, choose the $S\_i$ which minimizes $\frac{w\_i}{\min(|\hat{S}\_i|, Z)}$ where $Z$ is the number of elements we still need to get to complete $p|E|$ elements. Now we can guaranteed that there is an $S\_i$ for which the above is bounded by $OPT/Z$ (where now $OPT$ is the optimal for the partial set cover). To see this, suppose an optimal solution is the collection of sets $S\_1=\{xx|...\}$ $S\_2=\{xxx|...\}$, $S\_3=\{xxx|......\}$. In this notation, the $x$ represents an already covered element, and after the $|$ are elements which are not covered. Let $a\_1, a\_2, a\_3$ denote the number of such uncovered elements and suppose $a\_1, a\_2, a\_3\leq Z$. Then
$$min \{\frac{w\_1}{a\_1}, \frac{w\_2}{a\_2}, \frac{w\_3}{a\_3}\}\leq \frac{w\_1+w\_2+w\_3}{a\_1+a\_2+a\_3} = \frac{OPT}{a\_1+a\_2+a\_3} \leq \frac{OPT}{Z}.$$

Of course, if any of the $a\_i$'s is larger than $Z$ then it is replaced by $Z$ in the above inequalities and they hold.

The starting $Z$ is $Z\_0=p|E|$, and a similar analysis as for the full set cover leads to a total weight bounded by $OPT \cdot H\_{Z\_0}$.

> **Comments:**
> **username_3**: FWIW I guess the latter algorithm is a special case of Wolsey's generalization of the greedy set-cover algorithm ([minimizing a linear function subject to a submodular constraint](http://scholar.google.com/scholar?q=author:%22L+Wolsey%22+intitle:%22+An+analysis+of+the+greedy+algorithm+for+the+submodular+set+covering+problem%22)).  
> **username_5**: Wolsey's analysis proves a slightly stronger bound of $H_{d}$ where $d$ is the minimum of the maximum set size and $p|E|$.  

---

