9.3. Set Cover via Layering

Layering is an interesting technique that tries to slice a problem into layer (subproblems) that are easy to solve, at least approximately, and such that a good solution to the whole input can be obtained from good solutions of the layers.

In the context of set cover, the idea is to decompose the weight of each set into a sum of weights, \(w_S = w^1_S + \cdots + w^k_S\), such that each weight function \(w^i\) has a particular structure that helps us to find a good solution with respect \(w^i\). Then we combine the solutions computed with respect to \(w^1, \ldots, w^k\) into a single solution with respect to \(w\) and prove that this does not change the approximation ratio.

The weight functions we are interested in are called degree-weighted weight functions. A weight function \(w\) is degree-weighted if there exists a constant \(\alpha\) such that \(w_S = \alpha|S|\) for every set \(S \in \mathcal{S}\). The name "degree-weighted" stems from the fact that in the conversion of the vertex cover problem to a set cover problem shown in {{ref=fig:vc-set-cover}}, the size of the set \(S_v\) corresponding to each vertex \(v\) is exactly the degree of \(v\). The weight of \(S_v\) is then proportional to the degree of \(v\).

The usefulness of degree-weighted weight functions stems from the following observation:

Observation 9.3: If \(w\) is a degree-weighted cost function, then \(\mathcal{C} = \mathcal{S}\) is a set cover of \(U\) of weight 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: Let \(\mathcal{C}^*\) be an optimal set cover for \(U\). Since every element in \(U\) is covered by at least one set in \(\mathcal{C}^*\), we have \(\sum_{S \in \mathcal{C}^*} |S| \ge n\) and thus \(\mathrm{OPT} = \sum_{S \in \mathcal{C}^*} w_S = \sum_{S \in \mathcal{C}^*} \alpha|S| \ge \alpha n\). Since every element in \(U\) occurs in at most \(f\) sets in \(\mathcal{S}\), we have \(\sum_{S \in \mathcal{S}} |S| \le fn\) and thus \(\sum_{S \in \mathcal{S}} w_S = \sum_{S \in \mathcal{S}}\alpha|S| \le \alpha f n \le f \cdot \mathrm{OPT}\). ▨