Volume 11 (2015) Article 7 pp. 221-235
APPROX-RANDOM 2012 Special Issue
The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
Revised: July 22, 2014
Published: June 9, 2015
[PDF (262K)]    [PS (920K)]    [PS.GZ (280K)]
[Source ZIP]
Keywords: set-cover, PCP, Sliding Scale Conjecture, Projection Games Conjecture
ACM Classification: F.2.2, G.1.6
AMS Classification: 68W25

Abstract: [Plain Text Version]

$\newcommand\NP{\mathsf{NP}}$

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).