Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > TAXONOMY LABELING:
Reports tagged with taxonomy labeling:
TR07-105 | 21st September 2007
Jelani Nelson

A Note on Set Cover Inapproximability Independent of Universe Size

Revisions: 1

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 ... more >>>




ISSN 1433-8092 | Imprint