4
$\begingroup$

I have a question based on 3-Hitting Set problem. In this problem, we are given a universal set U of size n and a set of subsets S such that $\forall $ s $\in$ S |s|<=3. FOr this problem, Integer programming formulation is given by $x_{a}+x_{b}+x_{c} >=1 $ (a,b,c) $\in$ S

$\forall x_{i} \in $(1,0) where $i=1,2 \ldots n $

minimize $\sum x_{i} $

where each variable $x_i$ corresponds to element $i\in$ U.

A Linear programming relaxation would be 0<=$x_{i}$=<1 instead of $x_{i} \in$ {1,0}

After performing linear programming we know that In Every s $\in$S x_{a}+x_{b}+x_{c} >=1 at least one of $x_{i}>=\frac{1}{3}$ so $x_{i}>=\frac{1}{3}$ is made as 1 and the corresponding elements are selected in the solution. There may exist a set s such that $x_{a}+x_{b}+x_{c} >=1$ so that $x_{a},x_{b},x_{c}>=\frac{1}{3}$ and we will be picking all three elements. This way, we will get a three approximation after rounding $x_{a},x_{b},x_{c}$ to 1.

My question is

I look at a special case of 3 -hitting set H' in which size of each set s is exactly 3 and optimal solution for linear programming problem is $ \forall x_i =\frac{1}{3} $. Now, is it possible to improve the approximation factor to less than 3

$\endgroup$
  • $\begingroup$ You may want to consider what LP duality tells you: I think it gives that you can assign rational nonnegative weights to edges such that the weighted degree of each vertex is 1. This sounds related to whether the problem is easier on "regular" instances where every vertex appears in the same number of sets. $\endgroup$ – daveagp Oct 8 '10 at 10:55
8
$\begingroup$

What you've defined is the vertex cover problem for 3-uniform hypergraphs. Khot and Regev showed that if the unique games conjecture is true, then it is NP-hard to get an approximation of $3-\epsilon$ for this problem.

$\endgroup$
  • $\begingroup$ it is Np-hard for general 3-hitting set problem but here there is additional information that linear programming gives a optimal solution as each $ x_i=\frac{1}{3}$ for i=1,2 $\ldots$n. Is this information will not help us in better approximation. $\endgroup$ – Prabu Oct 9 '10 at 5:24
  • $\begingroup$ not sure why that makes a difference. You'll always get an optimal solution to the LP-relaxation in polytime. The problem is rounding it back. $\endgroup$ – Suresh Venkat Oct 9 '10 at 6:15
  • $\begingroup$ Since vertex cover related to this problem .Let me state the problem in terms of vertex cover .Given a Graph G(V,E) ,Integer programming formulation for vertex cover is $x_{i} + x_{j}>=1$ where (i,j) $\in$ E through LP-relaxation we get a 2- approximation. Now i give a special graph G' with the property that optimal solution for linear programming is $x_{i}= \frac{1}{2}$. Is this approximation can not improved over 2 for these special graph G' $\endgroup$ – Prabu Oct 9 '10 at 6:37
  • $\begingroup$ but that's what the Khot-Regev paper is about: these special (hyper)graphs that are regular and have a uniform assignment in the LP of the kind you describe. $\endgroup$ – Suresh Venkat Oct 9 '10 at 7:00

Your Answer

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

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