Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that ``hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the upper bound of $k$ for this problem, which is
attained by the straightforward greedy approximation algorithm. The
best previously known hardness result was due to
Holmerin, who showed the NP-hardness of approximating
E$k$-Vertex-Cover within a factor of $k^{1-\epsilon}$.

We present two constructions: one with a simple, purely combinatorial
analysis, showing E$k$-Vertex-Cover to be NP-hard to approximate to
within a factor $\Omega(k)$, followed by a stronger construction that
obtains the $(k-3-\epsilon)$ inapproximability bound. The latter
construction introduces a novel way of combining ideas from Dinur and
Safra's paper, and the notion of covering complexity
introduced by Guruswami, Hastad and Sudan. This also
allows us to prove a hardness factor of $(k-1-\epsilon)$ assuming the
hardness of $O(\log n)$-coloring a $c$-colorable graph for some fixed
$c \ge 3$.