Inapproximability of Minimum Vertex Cover on k-Uniform k-Partite Hypergraphs
DOI10.1137/130919416zbMATH Open1331.68089OpenAlexW2048411223MaRDI QIDQ3453563FDOQ3453563
Authors: Sushant Sachdeva, Rishi Saket, Venkatesan Guruswami 
Publication date: 27 November 2015
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/130919416
Recommendations
- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
- Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs
- scientific article; zbMATH DE number 2086690
- Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
- Inapproximability of hypergraph vertex cover and applications to scheduling problems
- An approximation algorithm for the partial vertex cover problem in hypergraphs
- On approximation of the vertex cover problem in hypergraphs
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
- A randomised approximation algorithm for the partial vertex cover problem in hypergraphs
- Inapproximability of \(b\)-matching in \(k\)-uniform hypergraphs
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cited In (10)
- Nearly optimal NP-hardness of vertex cover on \(k\)-uniform \(k\)-partite hypergraphs
- Partitioning a graph into small pieces with applications to path transversal
- On the Inapproximability of Vertex Cover on k-Partite k-Uniform Hypergraphs
- Approximating the discrete time-cost tradeoff problem with bounded depth
- Approximating the discrete time-cost tradeoff problem with bounded depth
- Title not available (Why is that?)
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Inapproximability of hypergraph vertex cover and applications to scheduling problems
- A new multilayered {PCP} and the hardness of hypergraph vertex cover
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs
This page was built for publication: Inapproximability of Minimum Vertex Cover on $k$-Uniform $k$-Partite Hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453563)
