9.2. Greedy Set Cover

The set cover problem is an extension of the vertex cover problem:

Given a universe \(U\) and a collection \(\mathcal{S}\) of subsets of \(U\) such that \(\bigcup_{S \in \mathcal{S}} = U\), a set cover is a subset \(\mathcal{C} \subseteq \mathcal{S}\) such that \(\bigcup_{S \in \mathcal{C}} = U\). In other word, \(\mathcal{C}\) contains at least one set from \(\mathcal{S}\) that includes each element of \(U\).

Unweighted Set Cover Problem: Given a universe \(U\) and a collection \(\mathcal{S}\) of subsets of \(U\) such that \(\bigcup_{S \in \mathcal{S}} = U\), find a set cover \(\mathcal{C} \subseteq \mathcal{S}\) of \(U\) of minimum size.

Weighted Set Cover Problem: Given a universe \(U\), a collection \(\mathcal{S}\) of subsets of \(U\) such that \(\bigcup_{S \in \mathcal{S}} = U\), and a weight function \(w : \mathcal{S} \rightarrow \mathbb{R}^+\), find a set cover \(\mathcal{C} \subseteq \mathcal{S}\) of \(U\) of minimum weight \(w(\mathcal{C}) = \sum_{S \in \mathcal{C}}w_S\).

As an example, consider a universe \(U = \{a,b,c,d,e\}\) and four subsets \(S_1 = \{a,b,c\}\), \(S_2 = \{b,d,e\}\), \(S_3 = \{a,b\}\), and \(S_4 = \{a,c\}\). The collection \(\mathcal{C} = \{S_1, S_2\}\) is a set cover because \(S_1 \mathcal{c}up S_2 = U\). It is a set cover of minimum size because we clearly cannot cover \(U\) with only a single set in \(\mathcal{S} = \{S_1, S_2, S_3, S_4\}\). Given a weight function defined as \(w_{S_1} = 3\), \(w_{S_2} = 4\), \(w_{S_3} = 1\), and \(w_{S_4} = 1\), however, it is not a minimum-weight set cover. Its weight is \(w(\mathcal{C}) = w_{S_1} + w_{S_2} = 7\), whereas the set \(\mathcal{C}' = \{S_2, S_3, S_4\}\) also covers \(U\) but has weight \(w(\mathcal{C}') = w_{S_2} + w_{S_3} + w_{S_4} = 6\).

Figure 9.4: Coming soon!

Clearly, any algorithm that can solve the weighted set cover problem can also solve the unweighted set cover problem because the unweighted set cover problem is a special case of the weighted set cover problem where every set has weight \(1\). By the following exercise, the restriction of the weight function in the weighted set cover problem to positive weights is not a serious one:

Exercise 9.1: Assume you are given an algorithm \(\mathcal{A}\) that computes a \(c\)-approximation of an optimal weighted set cover under the assumption that all sets have strictly positive weights. If \(c = 1\), then \(\mathcal{A}\) computes an optimal weighted set cover. Prove that you can use \(\mathcal{A}\) to also compute a \(c\)-approximation of an optimal weighted set cover when the sets have arbitrary weights.

In this section, we discuss a greedy algorithm that computes an \(O(\lg n)\)-approximation of an optimal weighted set cover.