ECCC-Report TR07-105https://eccc.weizmann.ac.il/report/2007/105Comments and Revisions published for TR07-105en-usTue, 30 Oct 2007 00:00:00 +0200
Revision 1
| A Note on Set Cover Inapproximability Independent of Universe Size Revision of: TR07-105 |
Jelani Nelson
https://eccc.weizmann.ac.il/report/2007/105#revision1In 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.
Tue, 30 Oct 2007 00:00:00 +0200https://eccc.weizmann.ac.il/report/2007/105#revision1
Paper TR07-105
| A Note on Set Cover Inapproximability Independent of Universe Size |
Jelani Nelson
https://eccc.weizmann.ac.il/report/2007/105In 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.
Thu, 25 Oct 2007 01:46:01 +0200https://eccc.weizmann.ac.il/report/2007/105