This blog will talking about the rounding algorithm of set cover problem.

Given a Set Cover Problem, a set of elements ${ E=\{e_1,\cdots,e_n\} }$, and subsets ${ S_1,\cdots, S_m \subseteq E}$ and for each ${ S_j }$ associated weight ${ w_j }$. We hope to find a set cover ${ I }$ such that ${ \bigcup_{j\in I} S_j = E }$. The objective is minimizing ${ \sum_{j \in I} w_j }$.

Deterministic Rounding Algorithm

We can still consider the ILP for set cover

$$ \begin{equation} \begin{aligned} &\text{minimize} && Z = \sum_{j=1}^{m } w_j x_j \\ &\text{subject to} && \sum_{j \in \{j\mid e_i \in S_j\}} x_j \geq 1, \quad \forall e_i \in E\\ & && x_j \in \{0,1\}, \quad \forall j = 1,2,\cdots, m\\ \end{aligned} \end{equation} $$

Solve the relaxed LP Problem,

$$ \begin{equation} \begin{aligned} &\text{minimize} && Z = \sum_{j=1}^{m} w_j x_j \\ &\text{subject to} && \sum_{j \in \{j\mid e_i \in S_j\}} x_j \geq 1, \quad \forall e_i \in E\\ & && x_j \geq 0, \quad \forall j = 1,2,\cdots, m\\ \end{aligned} \end{equation} $$

Let each ${ e_i }$ element appears in at most ${ f }$ sets

Hence, we can get a similar algorithm ${ 1 }$:

Step 1: Solve the LP and get optimal solution ${ x_1^*, x_2^*,\cdots, x_m^*}$ with value ${ Z_{LP}^* }$

Step 2: Add ${ j }$ to solution ${ I }$ if ${ x_j^* \geq 1/f}$

Theorem: Algorithm ${ 1 }$ ${ f }$-approximates the optimal set cover

1. Polynomial Run-time: LP can be solved in polynomial time and rounding in step 2 can be finished in linear time.

2. Feasibility: ${ \sum_{j \in \{j\mid e_i \in S_j\}} x_j^* \geq 1 }$, so at least some ${ x_j^* \geq 1/f }$, hence ${ \sum_{j \in \{j\mid e_i \in S_j\}} \hat{x}_j \geq 1 }$.

3. ${ f }$-approximation: for each ${ \hat{x_j} }$, if ${ x_j^* \geq 1/f }$, ${ \hat{x_j} = 1 }$, else ${ \hat{x_j} = 0 }$. And we know the minimum value of ILP ${ Z^*_{ILP} }$ will not less than the minimum value of LP ${ Z^*_{LP} }$ (because the feasible region of ILP is the subset of the feasible region of LP). Hence, we have

$$ \vert I \vert = \sum_{j = 1}^n w_j \hat{x}_j \leq f \sum_{j=1}^n w_j x^*_j = f Z^*_{LP}\leq f Z^*_{ILP} = f OPT $$

Hence we prove that Algorithm ${ 1 }$ is a ${ f }$-approximation algorithm. ${ \square }$

Dual Rounding Algorithm

We will try to consider the dual problem of set cover to get another approximation algorithm

• Charge each ${ e_i }$ a price ${ y_i \geq 0 }$ for its coverage by some set cover.

• And we need to make the total price of each ${ S_j }$ less that weight ${ w_j }$

• Find the highest total price can be charged to all elements.

$$ \begin{equation} \begin{aligned} &\text{maxmize} && Z = \sum_{i=1}^{n} y_i \\ &\text{subject to} && \sum_{i \in \{i\mid e_i \in S_j\}} y_i \leq w_j, \quad \forall j = 1,2,\cdots, m \\ & && y_i \geq 0, \quad \forall i = 1,2,\cdots, n\\ \end{aligned} \end{equation} $$

In fact this is a dual problem of set cover LP relaxation.

Weak dual property

Let ${ y }$ be any feasible solution to dual problem and ${ x }$ be any feasible solution to primal problem.

Because ${\sum_{j \in \{j\mid e_i \in S_j\}} x_j \geq 1 }$, we have

$$ \sum_{i=1}^n y_i \leq \sum_{i=1}^n \left(y_i \sum_{j \in \{j\mid e_i \in S_j\}} x_j \right) $$

We can re-write the right-side, we can first iterately each subset

$$ \sum_{i=1}^n \left(y_i \sum_{j \in \{j\mid e_i \in S_j\}} x_j \right) = \sum_{j=1}^m \left(x_j \sum_{i \in \{i\mid e_i \in S_j\}} y_i \right) $$

Addtionally, ${ \sum_{i \in {i\mid e_i \in S_j}} y_i \leq w_j }$, hence, we have

$$ \sum_{i=1}^n y_i \leq \sum_{j=1}^m \left(x_j \sum_{i \in \{i\mid e_i \in S_j\}} y_i \right) \leq \sum_{j=1}^m \left(x_j w_j \right) $$

hence, any feasible solution of dual problem is at most the minimum value of primal LP

$$ \sum_{i=1}^n y_i \leq Z_{LP}^* $$

Strong dual property

We don’t prove here, we have optimal value of primal and dual problem is equal

$$ \sum_{i=1}^n y^*_i = \sum_{j=1}^m x^*_j w_j $$

Algorithm ${ 2 }$

Step 1: Solve the Dual LP, and get optimal solution ${ y_1^*, y_2^*,\cdots, y_n^* }$ with value ${ Z_D^* }$

Step 2: Add ${ j }$ to solution ${ I }$ if the dual constraint for ${ S_j }$ is tight, that is ${ \sum_{i \in \{i\mid e_i \in S_j\}} y_i^* = w_j }$

Algorithm ${ 2 }$ is ${ f }$-approximation algorithm

Theorem Algorithm ${ 2 }$ ${ f }$-approximates the optimal set cover

Proof.

1. Polynomial Run-time: The Dual LP can be solved in polynomial time and Step 2 takes linear time

2. Feasibility: Suppose element ${ e_i }$ is not covered. Hence, for all the ${ S_j }$ such that ${ e_i \in S_j }$, their corresponding dual constraints is not tight (otherwise, we will pick up it in Step 2). So, we can inrease ${ y_i^* }$ while keeping the solution still feasible. Which contradicts to ${ Z_D^* }$ is optimal value.

3. ${ f }$-approximation: we pick ${ S_j, j\in I }$ because constraint is tight. So, we have ${ \sum_{j\in I} w_j = \sum_{j\in I} \sum_{i \in \{i\mid e_i \in S_j\}} y_i^* }$. Because, ${ e_i }$ appears at most in ${ f }$ subsets, so ${ \sum_{j\in I} w_j = \sum_{j\in I} \sum_{i \in \{i\mid e_i \in S_j\}} y_i^* \leq f \sum_{i =1}^n y_i^* = f Z_D^* = f Z_{LP}^* \leq f Z_{ILP}^* = f OPT }$