2
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.