The projection games conjecture and the NP-hardness of n-approximating Set-Cover
DOI10.1007/978-3-642-32512-0_24zbMATH Open1336.68104OpenAlexW2886103250MaRDI QIDQ3167403FDOQ3167403
Authors: Dana Moshkovitz 
Publication date: 2 November 2012
Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-32512-0_24
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cited In (14)
- On Hop-Constrained Steiner Trees in Tree-Like Metrics
- Deleting edges to restrict the size of an epidemic in temporal networks
- The Constant Inapproximability of the Parameterized Dominating Set Problem
- The projection games conjecture and the hardness of approximation of Super-SAT and related problems
- Tight approximation bounds for maximum multi-coverage
- Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
- PCPs via the low-degree long code and hardness for constrained hypergraph coloring
- Improved approximation algorithms for projection games (extended abstract)
- Time-approximation trade-offs for inapproximable problems
- When polynomial approximation meets exact computation
- Fractional set cover in the streaming model
- When polynomial approximation meets exact computation
- Improved approximation algorithms for projection games
- Title not available (Why is that?)
This page was built for publication: The projection games conjecture and the NP-hardness of \(\ln n\)-approximating Set-Cover
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3167403)
