Approximating vertex cover in dense hypergraphs

DOI10.1016/j.jda.2012.01.003zbMath1252.68135arXiv1012.2573MaRDI QIDQ450531

Richard Schmied, Marek Karpinski, Jean Cardinal, Claus Viehmann

Publication date: 13 September 2012

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.2573

zbMATH Keywords

approximation algorithms; vertex cover; set cover; \(k\)-partite \(k\)-uniform hypergraphs; approximation hardness; dense hypergraphs

Mathematics Subject Classification ID

05C65: Hypergraphs

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W25: Approximation algorithms

Related Items

Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Approximating the dense set-cover problem
• On approximation of the vertex cover problem in hypergraphs
• On a theorem of Lovász on covers in \(r\)-partite hypergraphs
• Improved non-approximability results for minimum vertex cover with density constraints
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• A better approximation ratio for the vertex cover problem
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• Vertex cover on 4-regular hyper-graphs is hard to approximate within 2 - ε
• On the power of unique 2-prover 1-round games
• Inapproximability of Hypergraph Vertex Cover and Applications to Scheduling Problems
• On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
• The Complexity of Perfect Matching Problems on Dense Hypergraphs
• Approximate Set Covering in Uniform Hypergraphs
• Non-approximability results for optimization problems on bounded degree instances
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Polynomial time approximation schemes for some dense instances of NP-hard optimization problems