9.3.1. A Recursive Algorithm

We obtain an \(f\)-approximate set cover with respect to an arbitrary weight function \(c\) using the following recursive algorithm, which implements the decomposition of the weight function \(w\) into degree-weighted weight functions \(w^1, \ldots, w^k\) that is the core idea of layering: The input to the algorithm is the universe \(U\) to be covered, the collection of sets \(\mathcal{S}\) to cover it with, and the weight function \(w\). For the top-level call, every set \(S \in \mathcal{S}\) is a subset of \(U\). In recursive calls, we only ensure that \(S \cap U \ne \emptyset\) for all \(S \in \mathcal{S}\) and that \(\bigcup_{S \in \mathcal{S}} S \supseteq U\), that is, that \(U\) can be covered using sets from \(\mathcal{S}\).

If \(U = \emptyset\), then the empty set is a valid set cover and clearly an optimal one, so we return it.

If \(U \ne \emptyset\), we start by splitting \(w\) into two weight functions \(w^1\) and \(w^2\) such that \(w^1\) is degree-weighted and \(w^2\) is non-negative: \(w_S = w^1_S + w^2_S\), \(w^1_S = \alpha|S \cap U|\) for some \(\alpha > 0\),¹ and \(w^2_S \ge 0\) for all \(S \in \mathcal{S}\). The choice of \(\alpha\) that ensures that \(w^2_S \ge 0\) for all \(S \in \mathcal{S}\) and that \(w^2_{S} = 0\) for at least one set \(S \in \mathcal{S}\) is

\[\alpha = \min_{S \in \mathcal{S}} \frac{w_S}{|S \cap U|}.\]

Let \(\mathcal{C}^1 = \{S \in \mathcal{S} \mid w^1_S = w_S\}\), let \(U' = U \setminus \bigcup_{S \in \mathcal{C}^1} S\), and let \(\mathcal{S}' = \{S \in \mathcal{S} \mid S \cap U' \ne \emptyset\}\). In other words, \(U'\) is the subset of elements in \(U\) not covered by \(\mathcal{C}^1\), and \(\mathcal{S}'\) is the subset of sets in \(\mathcal{S}\) that can be used to cover \(U'\). We compute a set cover \(\mathcal{C}^2\) of \(U'\) using sets from \(\mathcal{S}'\) by calling the algorithm recursively with \(U'\), \(\mathcal{S}'\), and the weight function \(w^2\) as arguments. The final set cover returned by the algorithm is \(\mathcal{C} = \mathcal{C}^1 \cup \mathcal{C}^2\).

Theorem 9.4: The layering algorithm computes a set cover of \(U\) using sets in \(\mathcal{S}\) whose weight is at most \(f \cdot \mathrm{OPT}\), where \(f\) is the maximum number of sets in \(\mathcal{S}\) that any element in \(U\) occurs in.

Proof: By induction on \(|U|\). Since \(U\), \(\mathcal{S}\), and \(w\) differ between recursive calls, we use \(\mathrm{OPT}(U, \mathcal{S}, w)\) to refer to the weight of an optimal set cover of \(U\) using sets from \(\mathcal{S}\) whose weights are given by the weight function \(w\).

If \(|U| = 0\), then the empty set returned by the algorithm is clearly a set cover of \(U\). Moreover, since every set \(S \in \mathcal{S}\) satisfies \(S \cap U \ne \emptyset\), we have \(\mathcal{S} = \emptyset\). Thus, the empty set is the only subset of \(\mathcal{S}\) that can be returned as a set cover. It is thus an optimal set cover.

If \(|U| > 0\), then let \(\mathcal{C}^*\) be an optimal set cover of \(U\) using sets in \(\mathcal{S}\) with weight function \(w\), that is, \(w(\mathcal{C}^*) = \mathrm{OPT}(U, \mathcal{S}, w)\). We need to prove that \(\mathcal{C}\) is a set cover of \(U\) and that \(w(\mathcal{C}) \le f \cdot w(\mathcal{C}^*)\).

First note that \(U' \subset U\) and that \(\bigcup_{S \in \mathcal{S}'} S \supseteq U'\). Indeed, the choice of \(\alpha\) ensures that there exists at least one set \(S \in \mathcal{S}\) that satisfies \(w^1_S = w_S\), so \(\mathcal{C}^1 \ne \emptyset\). Since every set \(S \in \mathcal{S}\) satisfies \(S \cap U \ne \emptyset\), this implies that \(U \cap \bigcup_{S \in \mathcal{C}^1} S \ne \emptyset\) and, thus, \(U' = U \setminus \bigcup_{S \in \mathcal{C}^1} S \subset U\). Since \(\bigcup_{S \in \mathcal{S}} S \supseteq U \supset U'\), we also have \(\bigcup_{S \in \mathcal{S}'} S \supseteq U'\) because every set \(S \in \mathcal{S} \setminus \mathcal{S}'\) satisfies \(S \cap U' = \emptyset\).

Now, since \(w^1\) is a degree-weighted weight function, we have

\[w^1(\mathcal{C}) \le w^1(\mathcal{S}) \le f \cdot \mathrm{OPT}\bigl(U, \mathcal{S}, w^1\bigr),\]

by Observation 9.3. Since \(\mathcal{C}^*\) is a set cover of \(U\), its weight \(w^1(\mathcal{C}^*)\) must satisfy²

\[w^1(\mathcal{C}^*) \ge \mathrm{OPT}\bigl(U, \mathcal{S}, w^1\bigr).\]

Thus,

\[w^1(\mathcal{C}) \le f \cdot w^1(\mathcal{C}^*).\tag{9.1}\]

Since \(U' \subset U\), the inductive hypothesis shows that \(\mathcal{C}^2 \subseteq \mathcal{S}'\) is a set cover of \(U'\) of weight

\[w^2\bigl(\mathcal{C}^2\bigr) \le f \cdot \mathrm{OPT}\bigl(U', \mathcal{S}', w^2\bigr).\]

Since every set \(S \in \mathcal{C}^* \setminus \mathcal{S}' \subseteq \mathcal{S} \setminus \mathcal{S}'\) satisfies \(S \cap U' = \emptyset\) but \(\mathcal{C}^*\) covers \(U \supseteq U'\), we have \(\bigcup_{S \in \mathcal{C}^* \cap \mathcal{S}'} S \supseteq U'\), that is, \(U'\) can be covered using only sets from \(\mathcal{C}^* \cap \mathcal{S}'\). Since \(\mathcal{C}^* \cap \mathcal{S}' \subseteq \mathcal{S}'\), an optimal set cover of \(U'\) using sets from \(\mathcal{S}'\) cannot be more expensive than an optimal set cover using sets from \(\mathcal{C}^* \cap \mathcal{S}'\): We have more opportunities to choose cheaper sets from \(\mathcal{S}'\) than from any proper subset of \(\mathcal{S}'\). Therefore,

\[\mathrm{OPT}\bigl(U', \mathcal{S}', w^2\bigr) \le \mathrm{OPT}\bigl(U', \mathcal{C}^* \cap \mathcal{S}', w^2\bigr).\]

Moreover,

\[\mathrm{OPT}\bigl(U', \mathcal{C}^* \cap \mathcal{S}', w^2\bigr) = \mathrm{OPT}\bigl(U', \mathcal{C}^*, w^2\bigr)\]

because every set \(S \in \mathcal{C}^* \setminus \mathcal{S}'\) satisfies \(S \cap U' = \emptyset\) and, due to its non-negative weight \(w^2_S\), can be omitted from any set cover of \(U'\) without increasing the set cover's weight. Since \(w^2\bigl(\mathcal{C}^2\bigr) \le f \cdot \mathrm{OPT}\bigl(U', \mathcal{S}', w^2\bigr)\), we thus have

\[w^2\bigl(\mathcal{C}^2\bigr) \le f \cdot \mathrm{OPT}\bigl(U', \mathcal{C}^*, w^2\bigr) \le f \cdot w^2(\mathcal{C}^*).\]

Finally, observe that \(w^2_S = w_S - w^1_S = 0\) for all \(S \in \mathcal{C}^1\). Thus,

\[w^2\bigl(\mathcal{C}^1\bigr) = 0\]

and

\[w^2(\mathcal{C}) = w^2\bigl(\mathcal{C}^1 \cup \mathcal{C}^2\bigr) = w^2\bigl(\mathcal{C}^2\bigr) \le f \cdot w^2(\mathcal{C}^*).\tag{9.2}\]

Since \(\bigcup_{S \in \mathcal{C}^1} S \supseteq U \setminus U'\) and \(\bigcup_{S \in \mathcal{C}^2} S \supseteq U'\), we have \(\bigcup_{S \in \mathcal{C}} S \supseteq U\), that is, \(\mathcal{C}\) is a set cover of \(U\). By (9.1) and (9.2), its weight is

\[w(\mathcal{C}) = w^1(\mathcal{C}) + w^2(\mathcal{C}) \le f \cdot w^1(\mathcal{C}^*) + f \cdot w^2(\mathcal{C}^*) = f \cdot w(\mathcal{C}^*) = f \cdot \mathrm{OPT}(U, \mathcal{S}, w).\ \text{▨}\]