__
Revision #1 to TR07-105 | 30th October 2007 00:00
__
#### A Note on Set Cover Inapproximability Independent of Universe Size Revision of: TR07-105

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

__
TR07-105 | 21st September 2007 00:00
__

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

**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. We conjecture that polynomial time $m^{1-\epsilon}$-approximation is impossible for any $\epsilon > 0$ unless SAT can be decided in subexponential time.