3
$\begingroup$

A common approach to approximating SETCOVER is the greedy algorithm (Algorithm 2.2 Vazirani). This algorithm greedily picks the most cost-effective subset at each iteration, removes covered elements, until there are no more uncovered elements.

However, one can go from the other end. Start with the full set, and iteratively remove the subset that is least cost-effective, and will not cause any elements to be uncovered, until there are no more such subsets.

In some sense, the second algorithm may be better because there wont be any redundant subsets in the solution. My question is, what is the name of this algorithm? Does it have the same runtime complexity and approximation ratio as the first one? I could not find any mention of this algorithm after a few hours of searching.

(Please include unweighted SETCOVER for comparison)

Edit: I see that the number of steps can in fact be as large as $(n-1)$ where $n$ is the number of subsets.

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ There is some work on the reverse greedy algorithm for (metric) k-medians. $\endgroup$ – Neal Young Oct 19 '16 at 23:43
4
$\begingroup$

The approximation guarantee will be significantly worse.

Assume you want to cover the set $U=\{1,\ldots,2n\}$. For every $i=1,\ldots,n$ define a set with n+1 elements by $S_i=\{i,n+1,\ldots,2n\}$. Assume we want to cover U with the sets $C=\{S_1,\ldots,S_n,U\}$, where $c(U)=2, c(S_i)=1$.

We would now start with $C$ ans see that the effectivity of the sets $S_i$ is $$\rho(S_i)=\frac{|S_i|}{c(S_i)}=\frac{n+1}{1}=n+1.$$

In contrast to this the effectivity of $U$ is $$\rho(U)=\frac{|U|}{c(U)}=\frac{2n}{2}=n<n+1.$$

Thus the reverse greedy would throw out the less effective $U$ leaving us with a solution of cost $n$ while there is a solution of cost $2$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Does a similar reasoning hold for unweighted setcover too? --- I see that the example wouldn't work for unweighted setcover. Could you add the unweighted reasoning to the solution? $\endgroup$ – rahul Jan 29 '16 at 17:52
  • $\begingroup$ @rahul I think instead of the set $U$ you could add the two sets $A=\{1,\ldots,n\},B=\{n+1,\ldots,2n\}$ then $\rho(A)=\rho(B)=|A|=|B|=n$ and the algorithm fails again. $\endgroup$ – Listing Jan 30 '16 at 11:48
  • $\begingroup$ @Listing, I think I understand your explanation. $\rho(A) = n$ and $\rho(B) = n$, which are both lesser than $\rho(S_i) = n+1$, hence both gets thrown out. However, $A\cup{}B$ is a covering set of $U$ with cost $2$, in comparison with $\bigcup\limits_{i = 1..n} S_i$ with a cost $n$. On the other hand, using greedy, I choose $S_1$ first, and B second because B is more cost effective now compared to any of $S_{2..n}$, which gives me the cost of $2$. Is my understanding correct? I will accept this answer if it is included in the main body. $\endgroup$ – rahul Jan 30 '16 at 23:22
  • $\begingroup$ I think it can be simplified further. Say we have only $B = \{n+1 .. 2n\}$, and not $A$. In this case, once $B$ is discarded, every $S_i$ is required to completely cover $U$, i.e a cost of $n$ compared to the minimum $C = \{B, S_1\}$ which is 2. $\endgroup$ – rahul Jan 31 '16 at 0:25

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.