Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
Abteilung V

Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2011 Copyright 2011 Universität Bonn, Institut für Informatik, Abt. V


Approximability of Vertex Cover in Dense Bipartite Hypergraphs
Jean Cardinal, Marek Karpinski, Richard Schmied and Claus Viehmann
[Download PostScript] [Download PDF]

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.

Last Change: 11/05/14 at 10:57:39
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope