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.4175MaRDI 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
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.)
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
- Unnamed Item
- 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
