Let
\(\mathcal {H}=(V,\mathcal {E})\) be a hypergraph with set of vertices
\(V, n:=|V|\) and set of (hyper-)edges
\(\mathcal {E}, m:=|\mathcal {E}|\). Let
\(l\) be the maximum size of an edge,
\(\varDelta \) be the maximum vertex degree and
\(D\) be the maximum edge degree. The
\(k\)-partial vertex cover problem in hypergraphs is the problem of finding a minimum cardinality subset of vertices in which at least
\(k\) hyperedges are incident. For the case of
\(k=m\) and constant
\(l\) it known that an approximation ratio better than
\(l\) cannot be achieved in polynomial time under the unique games conjecture (UGC) (Khot and Ragev J Comput Syst Sci, 74(3):335–349,
2008), but an
\(l\)-approximation ratio can be proved for arbitrary
\(k\) (Gandhi et al. J Algorithms, 53(1):55–84,
2004). The open problem in this context has been to give an
\(\alpha l\)-ratio approximation with
\(\alpha < 1\), as small as possible, for interesting classes of hypergraphs. In this paper we present a randomized polynomial-time approximation algorithm which not only achieves this goal, but whose analysis exhibits approximation phenomena for hypergraphs with
\(l\ge 3\) not visible in graphs: if
\(\varDelta \) and
\(l\) are constant, and
\(2\le l\le 4\varDelta \), we prove for
\(l\)-uniform hypergraphs a ratio of
\(l\left( 1-\frac{l-1}{4\varDelta }\right) \), which tends to the
optimal ratio 1 as
\(l\ge 3\) tends to
\(4\varDelta \). For the larger class of hypergraphs where
\(l, l \ge 3\), is not constant, but
\(D\) is a constant, we show a ratio of
\(l(1-1/6D)\). Finally for hypergraphs with non-constant
\(l\), but constant
\(\varDelta \), we get a ratio of
\( l (1- \frac{2 - \sqrt{3}}{6\varDelta })\) for
\(k\ge m/4\), leaving open the problem of finding such an approximation for
\(k < m/4\).