ECCC - TR11-098

ECCC

Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login

Register

Classic Style

REPORTS > DETAIL:

Paper:

TR11-098 | 11th July 2011 13:00

Tight Approximation Bounds for Vertex Cover on Dense k-Partite Hypergraphs

Contact

Add Comment

TR11-098 Authors: Marek Karpinski, Richard Schmied, Claus Viehmann
Publication: 11th July 2011 13:28
Downloads: 3723

Keywords:

Approximation Complexity, Dense k-Partite Instances, Unique Games Conjecture, Vertex Cover

Abstract:

We establish almost tight upper and lower approximation bounds for the Vertex Cover problem on dense k-partite hypergraphs.

ISSN 1433-8092 | Imprint