Revised: July 22, 2014
Published: June 9, 2015
Abstract: [Plain Text Version]
We establish a tight $\NP$-hardness result for approximating the SET-COVER problem based on a strong PCP theorem. Our work implies that it is $\NP$-hard to approximate SET-COVER on instances of size $N$ to within $(1-\alpha)\ln N$ for arbitrarily small $\alpha>0$. Our reduction establishes a tight trade-off between the approximation accuracy $\alpha$ and the running time $\exp(N^{\Omega(\alpha)})$ assuming SAT requires exponential time.
The reduction is obtained by modifying Feige's reduction. The latter provides a lower bound of $\exp(N^{\Omega(\alpha/\log\log N)})$ on the time required for $(1-\alpha)\ln N$-approximating SET-COVER assuming SAT requires exponential time. The modification uses a combinatorial construction of a bipartite graph in which any coloring of the first side that does not use a color for more than a small fraction of the vertices, makes most vertices on the other side have all their neighbors colored in different colors.
In the conference version of this paper, the SET-COVER result was conditioned on a conjecture we call “The Projection Games Conjecture” (PGC), a strengthening of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games LABEL-COVER. More precisely, the prerequisite was a quantitative version of this conjecture that was slightly beyond what was known at the time of the paper's writing. Shortly afterward, Dinur and Steurer, based on a result by the author and Raz, proved the quantitative version of the conjecture sufficient for the SET-COVER result. More broadly, in this paper we discuss the Projection Games Conjecture and its applications to hardness of approximation, e.g., to polynomial hardness factors for the CLOSEST-VECTOR problem and to studying the behavior of CSPs around their approximability threshold.
A preliminary version of this paper appeared in the Proceedings of the 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2012).
Licensed under a Creative Commons Attribution License (CC-BY)