Publication: A Note on Set Cover Inapproximability Independent of Universe Size
Loading...
Open/View Files
Date
2007
Authors
Published Version
Published Version
Journal Title
Journal ISSN
Volume Title
Publisher
Hasso-Plattner-Institut
The Harvard community has made this article openly available. Please share how this access benefits you.
Citation
Nelson, Jelani. 2007. "A Note on Set Cover Inapproximability Independent of Universe Size." Electronic Colloquium on Computational Complexity (ECCC), Revision 1 of TR07-105.
Abstract
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.
Description
Other Available Sources
Research Data
Keywords
set cover, taxonomy labeling, approximation hardness
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material (LAA), as set forth at Terms of Service