A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
From MaRDI portal
Publication:5317188
DOI10.1137/S0097539704443057zbMath1079.68039MaRDI QIDQ5317188
Irit Dinur, Subhash A. Khot, Venkatesan Guruswami, Oded Regev
Publication date: 16 September 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539704443057
hardness of approximation; probabilistically checkable proof; hypergraph vertex cover; long-code; multilayered outer verifier
05C65: Hypergraphs
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Related Items
Distributed set cover approximation: Primal-dual with optimal locality, Approximating Partially Bounded Degree Deletion on Directed Graphs, Inapproximability of $H$-Transversal/Packing, The Minimum Substring Cover Problem, Hardness of approximate two-level logic minimization and PAC learning with membership queries, Precedence-constrained covering problems with multiplicity constraints, Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover, Min–max version of single-machine scheduling with generalized due dates under scenario-based uncertainty, On improved interval cover mechanisms for crowdsourcing markets, Online and Approximate Network Construction from Bounded Connectivity Constraints, Complexity of approximating CSP with balance/hard constraints, Approximation and hardness results for the maximum edge \(q\)-coloring problem, Partial multicovering and the \(d\)-consecutive ones property, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, Hardness of approximating the closest vector problem with pre-processing, Approximating vertex cover in dense hypergraphs, Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs, Register loading via linear programming, Optimization problems in multiple subtree graphs, Minimizing the sum of weighted completion times in a concurrent open shop, Approximability of sparse integer programs, Approximating integer programs with positive right-hand sides, The ordered covering problem, The minimum substring cover problem, Noise stability of functions with low influences: invariance and optimality, Cooperative TSP, Towards a characterization of constant-factor approximable finite-valued CSPs, Tight approximation bounds for dominating set on graphs of bounded arboricity, The \(k\)-hop connected dominating set problem: approximation and hardness, Complexity and lowers bounds for power edge set problem, Online budgeted maximum coverage, Precedence-constrained covering problems with multiplicity constraints, Approximation of set multi-cover via hypergraph matching, Metrical service systems with multiple servers, Restricted parameter range promise set cover problems are easy, Paging with request sets, Set cover problems with small neighborhood covers, Efficiency and complexity of price competition among single-product vendors, Primal-dual algorithms for precedence constrained covering problems, Vertex cover might be hard to approximate to within \(2 - \varepsilon \), Strong hardness of approximation for tree transversals, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs, Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs, Primal-Dual Algorithms for Precedence Constrained Covering Problems
