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.68104OpenAlexW2886103250MaRDI 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
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)
Related Items (12)
Deleting edges to restrict the size of an epidemic in temporal networks ⋮ Time-approximation trade-offs for inapproximable problems ⋮ PCPs via the low-degree long code and hardness for constrained hypergraph coloring ⋮ Parameterized exact and approximation algorithms for maximumk-set cover and related satisfiability problems ⋮ When polynomial approximation meets exact computation ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Fractional Set Cover in the Streaming Model. ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ When polynomial approximation meets exact computation ⋮ Improved approximation algorithms for projection games ⋮ On Hop-Constrained Steiner Trees in Tree-Like Metrics ⋮ Tight approximation bounds for maximum multi-coverage
This page was built for publication: The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
