Pages that link to "Item:Q5317188"
From MaRDI portal
The following pages link to A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover (Q5317188):
Displayed 36 items.
- Complexity of approximating CSP with balance/hard constraints (Q315529) (← links)
- Approximation and hardness results for the maximum edge \(q\)-coloring problem (Q350721) (← links)
- Partial multicovering and the \(d\)-consecutive ones property (Q408373) (← links)
- Towards strong nonapproximability results in the Lovász-Schrijver hierarchy (Q430828) (← links)
- Hardness of approximating the closest vector problem with pre-processing (Q430834) (← links)
- Approximating vertex cover in dense hypergraphs (Q450531) (← links)
- Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs (Q491613) (← links)
- Register loading via linear programming (Q494793) (← links)
- Optimization problems in multiple subtree graphs (Q531599) (← links)
- Minimizing the sum of weighted completion times in a concurrent open shop (Q613333) (← links)
- Approximability of sparse integer programs (Q634673) (← links)
- Approximating integer programs with positive right-hand sides (Q656570) (← links)
- The ordered covering problem (Q722532) (← links)
- The minimum substring cover problem (Q958306) (← links)
- Noise stability of functions with low influences: invariance and optimality (Q974039) (← links)
- Cooperative TSP (Q982655) (← links)
- Towards a characterization of constant-factor approximable finite-valued CSPs (Q1671996) (← links)
- Tight approximation bounds for dominating set on graphs of bounded arboricity (Q1675919) (← links)
- The \(k\)-hop connected dominating set problem: approximation and hardness (Q1679503) (← links)
- Complexity and lowers bounds for power edge set problem (Q1711663) (← links)
- Approximation of set multi-cover via hypergraph matching (Q2207501) (← links)
- Metrical service systems with multiple servers (Q2258084) (← links)
- Restricted parameter range promise set cover problems are easy (Q2258109) (← links)
- Paging with request sets (Q2272199) (← links)
- Set cover problems with small neighborhood covers (Q2322696) (← links)
- Efficiency and complexity of price competition among single-product vendors (Q2407455) (← links)
- Primal-dual algorithms for precedence constrained covering problems (Q2408089) (← links)
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \) (Q2475406) (← links)
- Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes (Q2968149) (← links)
- Nearly Optimal NP-Hardness of Vertex Cover on k-Uniform k-Partite Hypergraphs (Q3088105) (← links)
- Using the FGLSS-Reduction to Prove Inapproximability Results for Minimum Vertex Cover in Hypergraphs (Q3088179) (← links)
- Primal-Dual Algorithms for Precedence Constrained Covering Problems (Q3453300) (← links)
- Approximating Partially Bounded Degree Deletion on Directed Graphs (Q5240368) (← links)
- Inapproximability of $H$-Transversal/Packing (Q5348212) (← links)
- The Minimum Substring Cover Problem (Q5443381) (← links)
- Hardness of approximate two-level logic minimization and PAC learning with membership queries (Q5920702) (← links)