Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed




Revision #1
Authors: Jelani Nelson
Accepted on: 30th October 2007 00:00
Downloads: 3754
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
Downloads: 3850
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. We conjecture that polynomial time $m^{1-\epsilon}$-approximation is impossible for any $\epsilon > 0$ unless SAT can be decided in subexponential time.



ISSN 1433-8092 | Imprint