Nelson, Jelani2017-09-252007Nelson, Jelani. 2007. "A Note on Set Cover Inapproximability Independent of Universe Size." Electronic Colloquium on Computational Complexity (ECCC), Revision 1 of TR07-105.1433-8092http://nrs.harvard.edu/urn-3:HUL.InstRepos:33946932In 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.en-USset covertaxonomy labelingapproximation hardnessJournal Article2015-01-13Jelani Nelson2017-09-25