# Partial cover approximation

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.

• 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 Apr 15 '16 at 15:36
• $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 Apr 15 '16 at 20:43
• It is solvable, and @tranisstor's example is not an issue. hint: the approximation factor is $O(\log(1/(1-p)))$. – Sasho Nikolov Apr 16 '16 at 3:14
• You mean do the greedy algorithm for the set cover problem until you have less than (1-p)m elements left? – John Harrison Apr 16 '16 at 12:11
• 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 Apr 16 '16 at 17:57

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}$.