This blog will talking about a randomized rounding algorithm.

In Algorithm ${ 1 }$, we round a variable ${ x_j^* }$ to ${ 1 }$ if ${ x_j^* \geq \frac{1}{f} }$.

For randomized Algorithm, we will decided the way to round the variable by probability. For variable ${ x_j^* }$ we will define a random variable ${ X_j }$, and define ${ Pr[X_j = 1] = x_j^* }$, ${ Pr[X_j = 0] = 1- x_j^* }$.

The expected value of the objective is optimal by linearity expectation.

$$ E\left[\sum_{j=1}^m w_j X_j \right] = \sum_{j=1}^m w_j Pr[X_j = 1] = \sum_{j=1}^m w_j x_j^* = Z_{LP}^* $$

However, the solution is feasible with very low probability.

$$ Pr[e_i \text{ is not covered}] = \prod_{j \in \{e_i \in S_j\}} 1 - x_j^* $$

And we know ${\forall x \in [0,1], 1 -x \leq e^{-x} }$. Thus we have,

$$ Pr[e_i \text{ is not covered}] = \prod_{j \in \{e_i \in S_j\}} 1 - x_j^* \leq \prod_{j \in \{e_i \in S_j\}} e^{-x_j^*} = e^{-\sum_{j \in \{e_i \in S_j\}} x_j^*} $$

And by LP constraint, we have ${ \sum_{j \in {e_i \in S_j}} x_j^* \geq 1 }$, so

$$ Pr[e_i \text{ is not covered}] = \prod_{j \in \{e_i \in S_j\}} 1 - x_j^* \leq \prod_{j \in \{e_i \in S_j\}} e^{-x_j^*} = e^{-\sum_{j \in \{e_i \in S_j\}} x_j^*} \leq e^{-1} $$

Algorithm ${ 6 }$

Step 1: Solve the relaxed LP

Step 2: add ${ j }$ to solution ${ I }$ with probability ${ \min \{ 1, K x_j^*\} }$. (take ${ K = c \ln n, c\geq 2 }$)

High probability of feasible solution

For any element ${ e_i }$, if ${ K x_j^* \geq 1 }$ for some ${ j }$ such that ${ e_i \in S_j }$, then ${ S_j }$ covers ${ e_i }$. Else, we have

$$ Pr[e_i \text{ is not covered}] = \prod_{j \in \{e_i \in S_j\}} 1 - K x_j^* \leq \prod_{j \in \{e_i \in S_j\}} e^{- K x_j^*} = e^{-\sum_{j \in \{e_i \in S_j\}} K x_j^*} \leq e^{-K} $$

Because, ${ K = c \ln n }$, we get

$$ Pr[e_i \text{ is not covered}] \leq e^{-K} = n^{-c} $$

By union bound (Boole’s inequality), we have

$$ Pr[\text{there exists some uncovered element}] = Pr\left[\bigcup_{e_i \in E } e_i \text{ is not covered}\right] \leq \sum_{i=1}^n Pr[e_i \text{ is not covered}]\leq \sum_{i=1}^n n^{-c} = n^{-c+1} $$

For ${ c \geq 2 }$, the probability to produce feasible solution is at least ${ 1 - \frac{1}{n} }$

Algorithm ${ 6 }$ is ${ 2c \ln n }$-approximation

It’s easy to get the expectation of all solution

$$ E\left[\sum_{j=1}^m w_j X_j \right] = \sum_{j=1}^m w_j Pr[X_j = 1] \leq \sum_{j=1}^m w_j K x_j^* = K Z_{LP}^* $$

However, we would like to bound the expecatation of feasible solution, let ${ F }$ be the event that solution is feasible, and ${ \bar{F} }$ be complement of this event. We know

$$ E\left[\sum_{j=1}^m w_j X_j \right] = E\left[\sum_{j=1}^m w_j X_j \middle| F \right] Pr[F] + E\left[\sum_{j=1}^m w_j X_j \middle| \bar{F} \right] Pr[\bar{F}] \geq E\left[\sum_{j=1}^m w_j X_j \middle| F \right] Pr[F] $$

Hence, we have

$$ E\left[\sum_{j=1}^m w_j X_j \middle| F \right] \leq \frac{1}{Pr[F]} E\left[\sum_{j=1}^m w_j X_j \right] \leq \frac{c \ln n Z_ {LP}^*}{1 - n^{1-c}} \leq \frac{c \ln n Z_{LP}^*}{1 - n^{-1}} \leq \frac{c \ln n Z_{LP}^*}{1 - 2^{-1}} = 2 c \ln n Z_{LP}^* \leq 2 c \ln n Z_{ILP}^* =2 c \ln n OPT $$