×

zbMATH — the first resource for mathematics

A threshold of \(\ln n\) for approximating set cover. (English) Zbl 1065.68573

MSC:
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDF BibTeX XML Cite
Full Text: DOI