<p>What you've defined is the vertex cover problem for 3-uniform hypergraphs. <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.4748&amp;rep=rep1&amp;type=pdf">Khot and Regev</a> showed that if the unique games conjecture is true, then it is NP-hard to get an approximation of $3-\epsilon$ for this problem. </p>

CC BY-SA 2.5
2010-10-09T05:24:01.480Z
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.
Prabu 
CC BY-SA 2.5
2010-10-09T06:15:13.143Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-10-09T06:37:22.740Z
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'
Prabu 
CC BY-SA 2.5
2010-10-09T07:00:35.033Z
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.
Suresh Venkat
CC BY-SA 2.5
2010-10-08T22:08:02.110Z
2010-10-08T22:08:02.110Z
Suresh Venkat
<p>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|&lt;=3.
FOr this problem, Integer programming formulation is given by 
$x_{a}+x_{b}+x_{c} >=1 $ (a,b,c) $\in$ S </p>

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

<p>minimize $\sum x_{i} $</p>

<p>where each variable $x_i$ corresponds to element $i\in$ U.</p>

<p>A Linear programming relaxation would be 
0&lt;=$x_{i}$=&lt;1 instead of $x_{i} \in$ {1,0}  </p>

<p>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.</p>

<p>My question is </p>

<p>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 </p>

CC BY-SA 2.5
2010-10-08T10:55:42.467Z
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.
daveagp
<ds.algorithms><np-hardness><approximation-algorithms>
Better approximation for special case of 3-hitting set
Prabu 
# Better approximation for special case of 3-hitting set

(Asked by: username_0 on 2010-10-08)

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

**Tags:** ds.algorithms, np-hardness, approximation-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2010-10-08. Score: 8 | Accepted answer

What you've defined is the vertex cover problem for 3-uniform hypergraphs. [Khot and Regev](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.4748&rep=rep1&type=pdf) showed that if the unique games conjecture is true, then it is NP-hard to get an approximation of $3-\epsilon$ for this problem.

> **Comments:**
> **username_0**: 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.  
> **username_2**: 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.  
> **username_0**: 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'  
> **username_2**: 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.  

---

