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

*

*A set cover problem is given

*Form the integer linear program.

*Obtain Linear program relaxation of the integer program

*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.
 A: 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.
