1
$\begingroup$

I need to find a 3-Approximation Algorithm for a weighted 3-Hitting Set.

I have an 2-Approximation Algorithm for a weighted 2-Hitting Set and in its explanation the Hitting-Set-Problem is formulated as an ILP. Then the LP-Relaxation for the ILP is created.

ILP:

minimize $\Sigma$ Wi*Xi

Subject to

$\Sigma$ Xi >= 1

Xi$\in${0,1}

LP:

minimize $\Sigma$ Wi*Xi

Subject to

Xi + Xj + Xk >= 1 {i,j,k}$\in$$E$

Xi >= 0 i$\in$$V$

And the Method is as follows:

You solve the LP-Relaxation and round it up to match the ILP.

It also gives the following definition for the Vertex-Cover $U$ $\subseteq$ $V$:

x* = (x*1, ... , x*n) is an optimal Solution for the LP-Relaxation and

$U$ = {$\mathcal{i}$ $\in$ $V$: x*i >= 1/2}.

SO $U$ is a weighted Vertex Cover, that is at most 2 times as big as the minimal Vertex Cover.

If I use this method to find a 3-Approximation Algorithm for a weighted 3-Hitting Set, is it really that simple to replace the 1/2 with 1/3, since now 3 vertices make 1 edge?

So $U$ = {$\mathcal{i}$ $\in$ $V$: x*i >= 1/3} ?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.