Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
DOI10.1016/j.jda.2014.12.010zbMath1337.68292arXiv1107.2000OpenAlexW1986334373MaRDI 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
approximation algorithmsvertex coverset cover\(k\)-partite \(k\)-uniform hypergraphsapproximation hardnessdense hypergraphs
Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Approximation algorithms (68W25)
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
This page was built for publication: Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
