Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs
From MaRDI portal
Publication:3088105
DOI10.1007/978-3-642-22935-0_28zbMath1343.68100arXiv1105.4175OpenAlexW2131906507MaRDI QIDQ3088105
Publication date: 17 August 2011
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1105.4175
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)
Related Items
Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
Cites Work
- On the hardness of approximating minimum vertex cover
- Uniformly cross intersecting families
- On a theorem of Lovász on covers in \(r\)-partite hypergraphs
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Proof verification and the hardness of approximation problems
- Schema mapping discovery from data instances
- 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
- Probabilistic checking of proofs
- A Parallel Repetition Theorem
- Non-approximability results for optimization problems on bounded degree instances
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Some optimal inapproximability results
- Combinatorial Pattern Matching
- Automata, Languages and Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
