In the Weighted Set Cover (WSC) problem, the input is a triple $\left(U,\mathcal{F},w\right)$ where $U$ is a universe of $n$ elements, $\mathcal{F}=\left\{ A_{1},A_{2},..,A_{m}\right\}$ is a family of $m$ sets such that each $A_{i}\subseteq U$ and $\bigcup_{A\in\mathcal{F}}A=U$ , and $w:\mathcal{F}\to\mathbb{R}_{>0}$ is a weight function that assigns positive weight to each set in $\mathcal{F}$ . A solution $S\subseteq\mathcal{F}$ for the WSC problem is valid if and only if $\bigcup_{A\in S}A=U$ , the weight of the solution is $w\left(S\right)=\sum_{A\in S}w\left(A\right)$ . Note that there is always a valid solution, and the goal in the WSC problem is to find such one with minimum weight.

We can reformulate the Weighted Set Cover problem as a system of linear equations as follows: For any set $A_{i}$ define an indicator variable $X_{i}\in\left\{ 0,1\right\}$ and let $w\left(X_{i}\right):=w\left(A_{i}\right)\cdot X_{i}$ , thus if $X_{i}=1$ then $w\left(X_{i}\right)=w\left(A_{i}\right)$ , and $w\left(X_{i}\right)=0$ otherwise. The objective is then to minimize $$\sum_{i=1}^{m}w\left(X_{i}\right)$$ subject to the $n$ following linear constrains $$\forall u\in U:\quad\sum_{i\text{ s.t. }u\in A_{i}}X_{i}\ge1$$

The final algorithm is just applying the $Alg\left(U,\mathcal{F},w\right)$ procedure $c$ independent times, and keeping the candidate solutions $S^{\left(1\right)},...,S^{\left(c\right)}$ , then returning the $S_{final}$ solution with minimum weight among those candidates.

We want to show that with high probability $w\left(S_{final}\right)\le c\cdot\log n\cdot w\left(S^{*}\right)$ . It is easy to see that for each iteration of the sub-procedure $Alg$ , the intermediate set $S_{t}$ has expected weight equals to the weight of the optimal fractional solution. Formally, $$\mathbb{E}\left[w\left(S_{t}\right)\right]=\sum_{i=1}^{m}w\left(A_{i}\right)\mathbb{E}\left[X_{i}\right]=\sum_{i=1}^{m}w\left(A_{i}\right)x_{i}=w\left(l_{t}^{*}\right)$$ note that the optimal value of all the fractional solutions is the same so we will remove the subscript $t$ . Next, we continue to calculate the expected weight of the output solution of the sub-procedure, that is, the weight of the candidate $S^{\left(i\right)}$

What is the probability that the returned solution $S_{final}$ is not valid? that is, there is at least one element $u\in U$ that is not covered by $S_{final}$ . We analyze that by first considering an arbitrary element $u$ and an intermediate solution $S_{t}$ of the sub procedure $Alg$ . Suppose that $u$ belongs to $k$ sets, and for simplicity suppose they are $A_{1},...,A_{k}$ . We know that their corresponding variables have $\sum_{i=1}^{k}x_{i}\ge1$ by the requirements of the linear system. The probability to leave all these sets outside $S_{t}$ is $$\prod_{i=1}^{k}\left(1-x_{i}\right)\le\prod_{i=1}^{k}e^{-x_{i}}\le e^{-1}$$ that is, the probability that an intermediate solution $S_{t}$ will not cover $u$ is up to $e^{-1}$ .