Theory of Computing
-------------------
Title : The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
Authors : Dana Moshkovitz
Volume : 11
Number : 7
Pages : 221-235
URL : http://www.theoryofcomputing.org/articles/v011a007
Abstract
--------
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).