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

DOI10.1016/j.jda.2014.12.010zbMath1337.68292arXiv1107.2000MaRDI QIDQ491613

Marek Karpinski, Claus Viehmann, Richard Schmied

Publication date: 18 August 2015

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

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

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.)

68W25: Approximation algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating vertex cover in dense hypergraphs
• Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
• Approximating the dense set-cover problem
• 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 \)
• Approximating Subdense Instances of Covering Problems
• COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY
• Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
• Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
• 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
• On the Computational Complexity of Combinatorial Problems
• 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