We prove that Minimum vertex cover on 4-regular hyper-graphs (or
in other words, hitting set where all sets have size exactly 4),
is hard to approximate within 2 - \epsilon.
We also prove that the maximization version, in which we
are allowed to pick B = pn elements in an n-vertex hyper-graph,
and are asked to cover as many edges as possible,
is hard to approximate
within 1/(1 - (1-p)^4) - \epsilon when p \geq 1/2 and
within ((1-p)^4 + p^4)/(1 - (1-p)^4) - \epsilon when
p < 1/2. From this follows that the general problem when B is part of
the input is hard to approximate within 16/15 - \epsilon.
These results also hold for k-regular hyper-graphs when k > 4.