Using known results regarding PCP,
we present simple proofs of the inapproximability
of vertex cover for hypergraphs.
Specifically, we show that
(1) Approximating the size of the minimum vertex cover
in $O(1)$-regular hypergraphs to within a factor of~1.99999 is NP-hard.
(2) Approximating the size ...
more >>>