15.02.2011

We study approximation complexity of the Vertex Cover problem restricted to dense and subdense balanced k-partite k-uniform hypergraphs. The best known approximation algorithm for the general k-partite case achieves an approximation ratio of k/2 which is the best possible assuming the Unique Game Conjecture. In this paper, we present approximation algorithms for the dense and the subdense nearly regular instances both with an approximation factor strictly better than k/2. On the other hand, we show that the latter approximation upper bound is almost tight under the Unique Games Conjecture.