Set Cover Problem: How to calculate the denominator?

Question

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

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

Zulfi.

Answer 1

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.