Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-155 | 22nd September 2015 20:34

Nearly Optimal NP-Hardness of Unique Coverage


Authors: Venkatesan Guruswami, Euiwoong Lee
Publication: 23rd September 2015 16:43
Downloads: 644


The {\em Unique Coverage} problem, given a universe $V$ of elements and a collection $E$ of subsets of $V$, asks to find $S \subseteq V$ to maximize the number of $e \in E$ that intersects $S$ in {\em exactly one} element. When each $e \in E$ has cardinality at most $k$, it is also known as {\em $1$-in-$k$ Hitting Set}, and admits a simple $\Omega(\frac{1}{\log k})$-approximation algorithm.

For constant $k$, we prove that $1$-in-$k$ Hitting Set is NP-hard to approximate within a factor $O(\frac{1}{\log k})$. This improves the result of Guruswami and Zhou [SODA'11, ToC'12], who proved the same result assuming the Unique Games Conjecture. For Unique Coverage, we prove that it is hard to approximate within a factor $O(\frac{1}{\log^{1 - \epsilon} n})$ for any $\epsilon > 0$, unless NP admits quasipolynomial time algorithms. This improves the results of Demaine et al. [SODA'06, SICOMP'08], including their $\approx 1/\log^{1/3} n$ inapproximability factor which was proven under the Random 3SAT Hypothesis. Our simple proof combines ideas from two classical inapproximability results for Set Cover and Constraint Satisfaction Problem, made efficient by various derandomization methods based on bounded independence.

ISSN 1433-8092 | Imprint