1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.