The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
From MaRDI portal
Publication:3167403
DOI10.1007/978-3-642-32512-0_24zbMath1336.68104MaRDI QIDQ3167403
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
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
The Constant Inapproximability of the Parameterized Dominating Set Problem, When polynomial approximation meets exact computation, When polynomial approximation meets exact computation, Improved approximation algorithms for projection games, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Time-approximation trade-offs for inapproximable problems, Deleting edges to restrict the size of an epidemic in temporal networks, Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems