Approximating vertex cover in dense hypergraphs

DOI10.1016/j.jda.2012.01.003zbMath1252.68135arXiv1012.2573OpenAlexW2075940489MaRDI 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 algorithmsvertex coverset cover\(k\)-partite \(k\)-uniform hypergraphsapproximation hardnessdense hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Minimal non-odd-transversal hypergraphs and minimal non-odd-bipartite hypergraphs ⋮ Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs

Cites Work

• Unnamed Item
• 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 \)
• 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

This page was built for publication: Approximating vertex cover in dense hypergraphs