I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round from 1/2 when converting it back to an ILP? Why aren't the bounds say, round down to 0 from 1/3 if a given vertex has value <= 1/3 and round up to 1 if said vertex has value > 1/3?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The constraints are $x_u + x_v \geq 1$ for all $uv \in E$. To get an integral solution, if you round up only values strictly more that $1/2$, then when your LP solution has $x^*_u = x^*_v = 1/2$, the rounding gives $x_u = x_v = 0$ which is not valid. So we must round from some threshold value $\alpha \leq 1/2$.
Can we choose $\alpha < 1/2$? Yes, but the approximation ratio is $1/\alpha$ (because if $x^*_u = \alpha$, then $x_u = 1$ and the associated cost goes from $w_u x^*_u$ to $w_u x_u$, hence is multiplied by $1 / \alpha$). So rounding from $1/3$ is worse that rounding from $1/2$, but is nevertheless a valid approximation algorithm.
