<p>The approximation guarantee will be significantly worse.</p>

<p>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$.</p>

<p>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.$$</p>

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

<p>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$.</p>

CC BY-SA 3.0
2016-01-29T17:52:40.127Z
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?
Rahul Gopinath
CC BY-SA 3.0
2016-01-30T11:48:15.443Z
@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.
Listing
CC BY-SA 3.0
2016-01-30T23:22:07.027Z
@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.
Rahul Gopinath
CC BY-SA 3.0
2016-01-31T00:25:19.570Z
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.
Rahul Gopinath
CC BY-SA 3.0
2016-01-29T10:05:03.107Z
2016-01-29T10:05:03.107Z
CS_Fan
<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>(Please include unweighted SETCOVER for comparison)</p>

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

CC BY-SA 3.0
2016-10-19T23:43:48.053Z
There is some work on the reverse greedy algorithm for (metric) k-medians.
Neal Young
<approximation-algorithms><set-cover><greedy-algorithms>
What is the reverse of greedy algorithm for setcover?
Rahul Gopinath
# What is the reverse of greedy algorithm for setcover?

(Asked by: username_0 on 2016-01-29)

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.

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

> **Comments:**
> **username_1**: There is some work on the reverse greedy algorithm for (metric) k-medians.  

---

## 1 answers

### Answer by username_2 on 2016-01-29. Score: 4 | Accepted answer

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

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

> **Comments:**
> **username_0**: 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?  
> **username_3**: @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.  
> **username_0**: @username_3, 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.  
> **username_0**: 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.  

---

