Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR07-105 | 30th October 2007 00:00

#### A Note on Set Cover Inapproximability Independent of Universe Size Revision of: TR07-105

Revision #1
Authors: Jelani Nelson
Accepted on: 30th October 2007 00:00
Keywords:

Abstract:

In the set cover problem we are given a collection of $m$ sets whose
union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection
whose union still covers $[n]$. We investigate the approximability of set cover
by an approximation ratio that depends only on $m$ and observe that, for any
constant $c < 1/2$, set cover cannot be approximated to within
$O(2^{\log^{1-1/(\log\log m)^c} m})$ unless SAT can be decided in slightly
subexponential time. The main ingredients in the observation are the
$\Omega(\log n)$ hardness of approximation proof of Lund and Yannakakis and a
hardness result for label cover due to Dinur and Safra.

### Paper:

TR07-105 | 21st September 2007 00:00

#### A Note on Set Cover Inapproximability Independent of Universe Size

TR07-105
Authors: Jelani Nelson
Publication: 25th October 2007 01:46
In the set cover problem we are given a collection of $m$ sets whose union covers $[n] = \{1,\ldots,n\}$ and must find a minimum-sized subcollection whose union still covers $[n]$. We investigate the approximability of set cover by an approximation ratio that depends only on $m$ and observe that, for any constant $c < 1/2$, set cover cannot be approximated to within $O(2^{\log^{1-1/(\log\log m)^c} m})$ unless SAT can be decided in slightly subexponential time. We conjecture that polynomial time $m^{1-\epsilon}$-approximation is impossible for any $\epsilon > 0$ unless SAT can be decided in subexponential time.