Loading jsMath...
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