Primal Dual algorithm for set cover

Question

I am having trouble understanding the approximation algorithm for set cover
using primal dual.
The entire approximation algorithm in a nutshell.

1. A set cover problem is given
2. Form the integer linear program.
3. Obtain Linear program relaxation of the integer program
4. Get the dual and find the optimal solution of the LP relaxation.

I have done upto this step, the example follows
$S = \{1, 2, 3, 4, 5, 6\}$
$S_1 = \{1, 2\}$, $S_2 = \{2, 3\}$ , $S_3 = \{1, 4, 5\}$ , $S_4 = \{2, 3, 6\}$
$w_1 = 35, w_2 = 36, w_3 = 37, w_4 = 38$

Dual and the optimal solution
$Z_{max} = y_1 + y_2 +y_3 +y_4 +y_5 +y_6$
subject to
$y_1 + y_2 <= 35$
$y_2 + y_3 <= 36$
$y_1 + y_4 + y_5 <= 37$
$y_2 + y_3 + y_6 <= 38$

Optimal solution
$y_1 = 35, y_2 = 0, y_3 = 36, y_4 = 2, y_5 = 0, y_6=2$

5th step

This is where I am stuck. The first 3 lines are basically initialize the variables
and run the loop until all elements are covered and the last line is just appending the chosen index $l$. The rest are going completely over my head.

Would really appreciate if anyone can explain the algorithm with the given example.

Answer 1

Start with $y=(0,0,0,0,0,0)$ and $I=\emptyset$ (so that $\cup_{j\in I}S_j=\emptyset$). The slack in the dual constraints is $(35, 36, 37, 38).$

Pick any element $e_i\in S$ not yet covered. I'll arbitrarily take $e_i=1$, which is contained in $S_\ell$ for $\ell\in \lbrace 1,3\rbrace.$ Increase $y_1$ until either dual constraint 1 or dual constraint 3 becomes binding. That happens when $y_1=35,$ at which point we have $y=(35,0,0,0,0,0)$ and dual slacks $(0, 36, 2, 38).$ The newly binding constraint corresponds to $\ell = 1,$ so we add $1$ to $I$. Now $I=\lbrace 1 \rbrace$ and $\cup_{j\in I}S_j= S_1 = \lbrace 1,2\rbrace.$

Again, pick any uncovered element. I'll choose $e_i = 3,$ contained in $S_\ell$ for $\ell \in \lbrace 2, 4\rbrace.$ Increase $y_3$ until either dual constraint 2 or dual constraint 4 becomes binding. That happens when $y_3=36,$ at which point $y=(35,0,36,0,0,0),$ slack is $(0,0,2,2),$ $\ell = 2,$ $I= \lbrace 1,3 \rbrace$ and $\cup_{j\in i}S_j = S_1 \cup S_3 = \lbrace 1,2,3 \rbrace.$

Hopefully the remaining steps are now clear.