This blog will talking about an algorithm that construct a solution for LP instead of solving LP.

Algorithm ${ 3 }$

Step 1: ${ I = \emptyset}$; ${\forall i , y_i = 0 }$

Step 2：While some ${ e_i }$ is uncovered, increase ${ y_i }$ untill some constraint become tight.

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

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

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

Proof.

1. Polynomial Run-time: We don’t solve the dual problem in fact. The running time is still in polynomial 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 }$ to make some constraint tight.

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 \leq f Z_D^* = f Z_{LP}^* \leq f Z_{ILP}^* = f OPT }$