Set Cover — Hao Wu

Set Cover Problem

Let $\Omega = \{ a_1, \ldots, a_n \}$ be a set, and $S_1, \ldots, S_m$ be subsets of $\Omega$ , such that $S_j$ is associated with weight $w_j \in \mathbb{R}^+$ for each $j \in [m]$ . The goal is solve the following the following optimization problem

\begin{array}{lll} &\min_{J \subseteq [m]} &\sum_{j \in J} w_j, \\ &\text{s.t.} &\cup_{j \in J} S_j = \Omega \end{array}

In case where $w_j = 1$ for each $j \in [m]$ , the problem is called the unweighted set cover problem.

Linear Programming

The linear program for the problem is

\begin{array}{llr} \min &\sum_{j \in [m]} w_j \cdot x_j \\ \text{s.t.} &\sum_{j : a_i \in S_j} x_j \ge 1 &\forall i \in [n]\\ &x_j \ge 0 &\forall j \in [m] \end{array}

The dual LP of the primal is

\begin{array}{llr} \max &\sum_{i \in [n]} y_i \\ \text{s.t.} &\sum_{i: a_i \in S_j} y_i \le w_j &\forall j \in [m]\\ &y_i \ge 0 &\forall i \in [n] \end{array}

Rounding the Optimal Primal Solution

For each element $i \in [n]$ , let $E_i \doteq \{ j \in [m] : a_i \in S_j \}$ , and let $C = \max_{i \in [n]} |E_i|$ .

Suppose that $x_j^*, j \in [m]$ be the optimal solution to the primal LP.

Theorem.
$J \doteq \left\{ j \in [m] : x_j^* \ge \frac{1}{C} \right\}$
is a $C$ -approximate solution to the set cover problem.

Proof. We prove first that $S_j, j \in J$ is a set cover, then we prove that it is a $C$ approximate one.

Feasibility. Since $x_j^*$ is the optimal solution to the primal LP, for each $i \in [n]$ , we have

\sum_{j : a_i \in S_j} x_j \ge 1.

Therefore, , there exists at least one $j \in E_i$ , s.t.,

x_j^* \ge \frac{1}{|E_i|} \ge \frac{1}{C}.

Approximation Ratio. The cost of the approximate solution is given by

\sum_{j \in J} w_j \le \sum_{j \in J} w_j \cdot \big( x_j^* \cdot C \big) \le C \cdot \sum_{j \in [m]} w_j \cdot x_j^*.

$\square$

Remark. This is a $2$ -approximation algorithm for the vertex cover problem, a special case of the set cover problem.

Rounding the Optimal Dual Solution

Let $y_i^*, i \in [n]$ be the optimal solution to the dual.

Theorem.
$J' \doteq \left\{ j \in [m] : \sum_{i: a_i \in S_j} y^*_i = w_j \right\}$
is a $C$ -approximate solution to the set cover problem.

Proof. We prove first that $S_j, j \in J'$ is a set cover, then we prove that it is a $C$ approximate one.

Feasibility. Suppose that there exits an uncovered element $a_k$ , which implies that for each $j \in E_k$ , it holds that

\sum_{i: a_i \in S_j} y^*_i < w_j.

But this implies that we can increase the value of $y_k^*$ , and therefore increase the value of $\sum_{i \in [n]} y_i^*$ , without violating the dual constraints, contradicting the $y_i^*, i \in [n]$ being optimal.

Approximation Ratio. The cost of the approximate solution is given by

\sum_{j \in J'} w_j = \sum_{j \in J'} \left( \sum_{i: a_i \in S_j} y^*_i \right) \le \sum_{i \in [n]} \left( \sum_{i: a_i \in S_j} y^*_i \right) \le C \cdot \sum_{i \in [n]} y^*_i,

where the last inequality holds, since each $y_i^*$ appears in at most $C$ constraints.

$\square$

Remark. Via complementary slackness, if $x_j^* > 0$ , we always have

\sum_{i : a_i \in S_j} y^*_i = w_j.

Since $J \doteq \left\{ j \in [m] : x_j^* \ge 1 / C \right\}$ , it holds that $J \subseteq J'$ . Therefore, rounding the primal solution do no worse than rounding the dual one.

The Primal-Dual Method

Rounding the optimal dual solution requires to solve the dual LP optimally, which could be slow even though the LP can be solved in polynomial time. The following algorithm overcomes this drawback by constructing only a feasible dual solution.

Algorithm. $\mathcal{A}_{primal \text{-} dual}$

$y_i \leftarrow 0$ , for each $i \in [n]$

$J \leftarrow \emptyset$

while $\exists a_k \notin \cup_{j \in J} S_j$ do

$\qquad$ increase $y_k$ until some constraint becomes tight,

$\qquad$ i.e., $\exists S_\ell$ with $a_k \in S_j$ , s.t., $\sum_{i: a_i \in S_\ell} y_i = w_\ell$

$\qquad$ $J \leftarrow J \cup \{ \ell \}$

Clearly the $y_i, i \in [n]$ is a feasible solution to the dual.

Theorem. Algorithm $\mathcal{A}_{primal \text{-} dual}$ returns a $C$ -approximate solution $J$ to the set cover problem.

Proof. We prove first that $S_j, j \in J$ is a set cover, then we prove that it is a $C$ approximate one.

Feasibility. Suppose that there exits an element $a_k$ that is not covered by $J$ , which implies that for each $j \in E_k$ , it holds that

\sum_{i: a_i \in S_j} y_i < w_j.

But this implies that we can increase the value of $y_k$ , and therefore increase the value of $\sum_{i \in [n]} y_i$ , without violating the dual constraints, contradicting $y_i$ being optimal.

Approximation Ratio. The cost of the approximate solution is given by

\sum_{j \in J} w_j = \sum_{j \in J} \left( \sum_{i: a_i \in S_j} y_i \right) \le \sum_{i \in [n]} \left( \sum_{i: a_i \in S_j} y_i \right) \le C \cdot \sum_{j \in [m]} y_i,

where the last inequality holds, since each $y_i$ appears in at most $C$ constraints.

$\square$

Randomized Rounding

We present a randomized algorithm based on the optimal solution $x_j^*$ for the primal LP.

Let $T \in \mathbb{N}^+$ be a positive integer to be determined later.

Algorithm. $\mathcal{A}_{rnd}$

for $t \in [T]$ do

$\qquad$ $J_t \leftarrow \emptyset$

$\qquad$ for each $j \in [m]$ do

$\qquad$ $\qquad$ add $j$ to $J_t$ with probability $x_j^*$

output $J \leftarrow \cup_{t \in [T]} J_t$

Theorem. The expected cost of $J$ is at most $T \cdot \sum_{j \in [m]} w_j \cdot x_j^*$ . Further, if $T = 2 \ln n$ , with probability at least $1 - 1 / n$ , $J$ is a set cover.

Proof.

Expected Cost. Since $j$ is included in $J_t$ with probability $x_j^*$ for each $j \in [m]$ , by linearity of expectation, the expected sum of weights of sets in $J_t$ is given by

\sum_{j \in [m]} w_j \cdot x_j^*.

Therefore, the expected cost of $J$ is at most $T \cdot \sum_{j \in [m]} w_j \cdot x_j^*$ .

Failure Probability. The probability that a fixed $a_i$ is not covered by $J_t$ is given by

\begin{aligned} \prod_{j : a_i \in S_j} (1 - x_j^*) \le \exp \left( - \sum_{j : a_i \in S_j} x_j^* \right) \le \exp (- 1). \end{aligned}

By independence, the probability that none of the $J_t$ covers $a_i$ is at most

\big( \exp(-1) \big)^T = \exp(-T) = 1 / n^2.

Applying union bound over all element $a_i \in \Omega$ finishes the proof.

$\square$

Greedy Algorithm

Finally, we discuss a greedy algorithm for the set cover problem.

We follows the convention that $x / 0 = \infty$ , $\forall x \in \mathbb{R}^+$ .

Algorithm. $\mathcal{A}_{greedy}$

$\hat S_j \leftarrow S_j$ , for each $j \in [m]$

$J \leftarrow \emptyset$

while $\cup_{j \in J} S_j \neq \Omega$ do

$\qquad$ $\ell \leftarrow \min_{j \in [m]} \left( w_j / |\hat S_j| \right)$

$\qquad$ $J \leftarrow J \cup \{ \ell \}$

$\qquad$ $\hat S_j \leftarrow \hat S_j \setminus S_\ell$ , $\forall j \in [m]$

For each $k \in \mathbb{N}^+$ , define $H_k = \sum_{i \in [k]} 1 / i$ .

Theorem. $\mathcal{A}_{greedy}$ outputs a $H_n$ approximate solution $J$ to the set cover problem.

Proof. When an $\ell$ is added to $J$ , it is easy to see that $\hat S_\ell \neq \emptyset$ , as otherwise $w_\ell / |\hat S_\ell| = \infty$ . Therefore we can charge the cost of $w_\ell$ among elements in $\hat S_\ell$ , with each elements $a_i \in \hat S_\ell$ obtaining a cost of

y_i \doteq w_\ell / |\hat S_\ell|.

Since each $a_i \in \Omega$ is charged exactly once, it holds that

\sum_{j \in J} w_j = \sum_{i \in [n]} y_i.

Our proof is based on the following lemma.

Lemma. For each $j \in [m]$ , it holds that
$\sum_{i : a_i \in S_j} y_i \le w_j \cdot H_{|S_j|}.$

We now finish the proof for the theorem, assuming the lemma holds. Let $D \doteq \max_{j \in [m} |S_j| \le n$ . For each $i \in [n]$ , define new variable $\hat y_i = y_i / H_D$ . Then the $\hat y_i$ is a feasible solution to the dual LP, and therefore $\sum_{i \in [n]} \hat y_i \le \text{OPT}$ , where $\text{OPT}$ is the value of the optimal solution to the set cover problem. We conclude that

\sum_{j \in J} w_j = \sum_{i \in [n]} y_i = H_D \cdot \sum_{i \in [n]} \hat y_i \le H_D \cdot \text{OPT}.

Proof of the Lemma. Suppose that the solution $J$ returned by $\mathcal{A}_{greedy}$ consists $t$ numbers $\ell_1, \ldots, \ell_t$ , indexed according to their orders added to $J$ .

For each $k \in [t]$ , define

r_k \doteq \Big| S_j \setminus \big( S_{\ell_1} \cup S_{\ell_2} \cup \ldots \cup S_{\ell_{k - 1}}) \Big|.

Note that $r_k$ is the number of new elements in $S_j$ that is covered by sets indexed by $J$ , before $\ell_k$ is added to $J$ . For convenience, let $r_0 = n$ . For each $k \in [t]$ , define $c_k = r_k - r_{k - 1}$ . We claim that for each $k \in [t]$ , it holds that

\sum_{i : a_i \in S_j \cap \hat S_{\ell_k}} y_i = c_k \cdot y_i \le c_k \cdot \frac{w_j}{r_k}.

If $S_j \cap \hat S_{\ell_k} = \emptyset$ , then $c_k = 0$ and the claim holds trivially. Otherwise, the criteria for picking $\ell_k$ by $\mathcal{A}_{greedy}$ ensures that for each $a_i \in S_j \cap \hat S_{\ell_k}$ , it holds that

y_i = \frac{w_{\ell_k} }{|\hat S_{\ell_k}|} \le \frac{w_j}{r_k}.

Therefore,

\begin{aligned} \sum_{i : a_i \in S_j} y_i &= \sum_{k \in [t]} \sum_{i : a_i \in S_j \cap \hat S_{\ell_k}} y_i \\ &\le \sum_{k \in [t]} c_k \cdot \frac{w_j}{r_k} \\ &\le \sum_{k \in [t]} w_j \left( \frac{1}{r_k} + \frac{1}{r_k - 1} + \ldots + \frac{1}{r_k - c_k + 1} \right) \\ &= w_j \sum_{k \in \big[ |S_j| \big]} \frac{1}{k} \\ &= w_j \cdot H_{|S_j|}. \end{aligned}

$\square$

Reference

[1] D. P. Williamson and D. B. Shmoys, The Design of Approximation Algorithms. Cambridge: Cambridge University Press, 2011.