0
$\begingroup$

I am trying to understand the set cover problem. I found the algorithm at: Set Cover which also contains the attached example:

3-Set Example

Somebody please guide me, how we calculate the denominator |S-C| and how we obtain C?

Zulfi.

$\endgroup$
2
  • $\begingroup$ That link didn't work for me. $\endgroup$
    – saulspatz
    May 10, 2020 at 20:26
  • $\begingroup$ @saulspatz, thanks I have updated the link. $\endgroup$
    – zak100
    May 10, 2020 at 23:15

1 Answer 1

1
$\begingroup$

This isn't the clearest set of notes I've ever seen. $C$ is the set of elements covered by the sets chosen so far, that is, the union of the chosen set. Originally, $C=\emptyset$ and the algorithm continues until $C=U$.

This is a greedy algorithm; at each stage, it picks the set with the lowest cost per newly-covered element. In the example, in the first round no elements are covered yet, so it's just the cost of the set divided by its cardinality:$$ \alpha(Z)=\frac77=1\\ \alpha(X)=\frac65=1.2\\ \alpha(Y)=\frac{15}{5}=3\\ $$ so $Z$ is chosen, and now $C=Z$

In the next round, the cost of the sets doesn't change, but they have fewer uncovered elements. Now we have $$ \alpha(X)=\frac63=2\\ \alpha(Y)=\frac{15}{5}=3$$ so $X$ is chosen, and now $C=Z\cup X$.

In the third round, only $Y$ remains. It doesn't really matter what the cost is, since we have to choose $Y$ but $$\alpha(Y)=\frac{15}{2}=7.5$$

One thing that makes the notes hard to follow is that in expressions like $$\frac{c(X)}{|S-C|}$$ $S$ is the loop variable, which happens to equal $X$ in this instance. It would be clearer, at least to me, if she has written $S$ in both places, or $X$ in both.

I hope this makes it clear to you.

$\endgroup$
4
  • $\begingroup$ Thanks. Plz help: (1)Why start with Z, cost is 7, cost of X is 6, we have to choose the least cost effective? (2) How are we choosing the denominators? In case of Z, denominators are 7, 5, 5, Z has 7 dots (or cardinality) but 5 are shareable and 2 are non-shareable? X has 5 shareable dots, 2 shared with Z and 3 shared with Y, denominators are 3 and 5 how?, Y has 5 elements 3 shareable with X and 2 non-shareable, denominator is 2, why? (3) What is the purpose of these 3 rounds? (4) What is the answer of set Cover? Example says optimal cost is 22? What is the cost in case of greedy algorithm? $\endgroup$
    – zak100
    May 11, 2020 at 4:24
  • 1
    $\begingroup$ 1. This is the problem statement. It doesn't make sense to ask why. 2. That's the data. It doesn't make sense to ask why. The denominators are the number of elements that will be covered if we choose set $S$ that weren't already covered. 3. The three rounds are the algorithm. 4. The answer is $X, Y, Z$ The cost is $6+7+15=28.$ $\endgroup$
    – saulspatz
    May 11, 2020 at 6:29
  • $\begingroup$ (1)Ok, I thought we are following the alg which says: Find the set whose cost effectiveness is smallest (2) Denominator is |S-C|, after round 1, C =7, I can’t understand how |S-C|= 3, 2 in round 2? (4) 6, 7, 15, is the given data, what is the purpose of our calculation in round 1, round 2, and round3, for determining the answer? $\endgroup$
    – zak100
    May 11, 2020 at 15:12
  • 1
    $\begingroup$ $C$ is the set of elements that have already been covered. After round $1$, $C=Z,\ |C|=7$. In round 2, I guess you are talking about the computation of $\alpha(X)$. In this case, $|S-C|=|X-Z|=3$ $\endgroup$
    – saulspatz
    May 11, 2020 at 15:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .