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

Mathematics Subject Classification ID

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)

Recommendations

• scientific article; zbMATH DE number 6474898
• A threshold of ln n for approximating set cover
• scientific article; zbMATH DE number 1256748
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• Improved approximation algorithms for projection games

Cited in

(14)

• The constant inapproximability of the parameterized dominating set problem
• When polynomial approximation meets exact computation
• PCPs via the low-degree long code and hardness for constrained hypergraph coloring
• Tight approximation bounds for maximum multi-coverage
• On Hop-Constrained Steiner Trees in Tree-Like Metrics
• Fractional set cover in the streaming model
• scientific article; zbMATH DE number 6474898 (Why is no real title available?)
• Time-approximation trade-offs for inapproximable problems
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• Deleting edges to restrict the size of an epidemic in temporal networks
• Parameterized exact and approximation algorithms for maximum \(k\)-set cover and related satisfiability problems
• When polynomial approximation meets exact computation
• Improved approximation algorithms for projection games
• Improved approximation algorithms for projection games (extended abstract)

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)