12.2. Set Cover via the Primal-Dual Schema

Let us use the set cover problem once again as a simple example to illustrate the use of the primal-dual schema to obtain approximation algorithms. We will obtain an \(f\)-approximation of an optimal set cover, where \(f\) is once again the maximum number of sets in \(\mathcal{S}\) that any element \(e \in U\) occurs in. Based on the primal LP (11.2) and the dual LP (11.3) of the set cover problem, we obtain the following \((1,f)\)-relaxed complementary slackness conditions:

• Primal complementary slackness: For all \(S \in \mathcal{S}\),

  \[\hat x_S = 0 \text{ or } \sum_{e \in S} \hat y_e = w_S.\]

• \(\boldsymbol{f}\)-Relaxed dual complementary slackness: For all \(e \in U\),

  \[\hat y_e = 0 \text{ or } \sum_{e \in S} \hat x_S \le f.\]

Note that we require strict primal complementary slackness (\(\alpha = 1\)). It is dual complementary slackness that we relax in this example.

We can once again interpret the dual LP as a packing LP, where we are required to pack values \(y_e\) associated with the elements in \(U\) into the sets in \(\mathcal{S}\) without overpacking any set: \(\sum_{e \in S} \hat y_e \le w_S\). Primal complementary slackness then states that we are allowed to include a set \(S \in \mathcal{S}\) in the set cover \(\mathcal{C}\) (\(\hat x_S = 1\)) only if it is tightly packed. We call \(S\) tight in this case.

This gives the following algorithm:

• We initialize \(\mathcal{C} = \emptyset\), which is equivalent to setting \(\hat x_S = 0\) for all \(S \in \mathcal{S}\), and we set \(\hat y_e = 0\) for all \(e \in U\).

  Note that the dual solution \(\hat y\) is feasible and that \(\hat x_S = 0\) for all \(S \in \mathcal{S}\) and \(\hat y_e = 0\) for all \(e \in U\) implies that \((1,f)\)-relaxed complementary slackness holds for the two solutions \(\hat x\) and \(\hat y\).

• As long as there are elements in \(U\) not covered by \(\mathcal{C}\) yet, we perform two operations:

  • First we pick an arbitrary uncovered element \(e\) and update the dual solution \(\hat y\) to create at least one tight set that contains \(e\).

  • Then we add all tight sets to \(\mathcal{C}\), which ensures that \(e\) is now covered by \(\mathcal{C}\).

Since each iteration covers at least one new element not covered before, we obtain a set cover after at most \(n = |U|\) iterations. Since we add only tight sets to the set cover, the computed solution satisfies primal complementary slackness. (We argue below that once a set becomes tight, it remains tight.) As we will see, \(f\)-relaxed dual complementary slackness holds trivially. Thus, the computed set cover is an \(f\)-approximation of an optimal set cover.

The details of the two steps in each iteration are as follows:

• Create new tight sets: Pick an uncovered element \(e \in U\) and increase \(\hat y_e\) by

  \[\delta = \min_{e \in S} \left( w_S - \sum_{e' \in S} \hat y_{e'} \right).\]

  This explicitly ensures that \(\sum_{e' \in S} \hat y_{e'} \le w_S\) for every set \(S\) that contains \(e\). For any set \(S\) that does not contain \(e\), the sum \(\sum_{e' \in S} \hat y_{e'}\) does not change. Thus, the dual solution \(\hat y\) remains feasible. The choice of \(\delta\) ensures that at least one set that contains \(e\) becomes tight.

• Cover more elements: Add all tight sets to \(\mathcal{C}\). Since the previous step creates at least one tight set that contains \(e\), this increases the number of elements covered by \(\mathcal{C}\).

Lemma 12.2: The above algorithm computes a set cover of weight at most \(f \cdot \mathrm{OPT}\).

Proof: Let \(\hat x\) and \(\hat y\) be the primal and dual solutions computed by the algorithm, where \(\hat x_S = 1\) if and only if \(S \in \mathcal{C}\). By Lemma 12.1, it suffices to verify that \(\hat x\) and \(\hat y\) are feasible primal and dual solutions and that they satisfy \((1,f)\)-relaxed complementary slackness.

We argued already that all updates of \(\hat y\) maintain the feasibility of this dual solution. At the end of the algorithm, every element in \(U\) is covered by \(\mathcal{C}\), so \(\hat x\) is a feasible primal solution.

To see that primal complementary slackness holds, we need to verify that all sets in \(\mathcal{C}\) at the end of the algorithm are tight. Each set \(S \in \mathcal{C}\) is tight when we add it to \(\mathcal{C}\). Thus, it suffices to verify that once a set becomes tight, it never becomes non-tight again.

Consider any iteration of the algorithm that aims to cover an element \(e\). For any set \(S \in \mathcal{S}\) that does not contain \(e\), \(\sum_{e' \in S} \hat y_{e'}\) does not change, so \(S\) remains tight if it was tight before. For any set \(S \in \mathcal{S}\) that does contain \(e\), \(\sum_{e' \in S} \hat y_{e'}\) increases by \(\delta\). Since \(\hat y\) is a feasible solution before we increase \(\hat y_e\) by \(\delta\), the choice of \(\delta\) implies that \(\delta \ge 0\). Thus, \(\sum_{e' \in S} \hat y_{e'}\) does not decrease, that is, \(S\) remains tight if it was tight before.

To verify \(f\)-relaxed dual complementary slackness, observe that every element \(e\) occurs in at most \(f\) sets in \(\mathcal{S}\). Thus, \(\sum_{e \in S} \hat x_S \le f\) whether \(\hat y_e = 0\) or not. ▨