A Note on Set Cover Inapproximability Independent of Universe Size
Jelani Nelson · Digital Access to Scholarship at Harvard (DASH) (Harvard University) · 2007
In the set cover problem we are given a collection of m sets whose union covers [n]=1n 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 c12 , set cover cannot be approximated to within O(2log1−1(loglogm)cm) unless SAT can be decided in slightly subexponential time. The main ingredients in the observation are the (logn) hardness of approximation proof of Lund and Yannakakis and a hardness result for label cover due to Dinur and Safra.