  We study the problem of computing the minimum vertex cover on k-uniform
k-partite hypergraphs when the k-partition is given. On bipartite graphs (k =
2), the minimum vertex cover can be computed in polynomial time. For general k,
the problem was studied by Lov\'asz, who gave a k/2 -approximation based on the
standard LP relaxation. Subsequent work by Aharoni, Holzman and Krivelevich
showed a tight integrality gap of (k/2 - o(1)) for the LP relaxation. While
this problem was known to be NP-hard for k >= 3, the first non-trivial
NP-hardness of approximation factor of k/4- \eps was shown in a recent work by
Guruswami and Saket. They also showed that assuming Khot's Unique Games
Conjecture yields a k/2 - \eps inapproximability for this problem, implying the
optimality of Lov\'asz's result.
  In this work, we show that this problem is NP-hard to approximate within k/2-
1 + 1/2k -\eps. This hardness factor is off from the optimal by an additive
constant of at most 1 for k >= 4. Our reduction relies on the Multi-Layered PCP
of Dinur et al. and uses a gadget - based on biased Long Codes - adapted from
the LP integrality gap of Aharoni et al. The nature of our reduction requires
the analysis of several Long Codes with different biases, for which we prove
structural properties of the so called cross-intersecting collections of set
families - variants of which have been studied in extremal set theory.
