Inapproximability Results
Lund & Yannakakis (1994) showed that set covering cannot be approximated in polynomial time to within a factor of, unless NP has quasi-polynomial time algorithms. Feige (1998) improved this lower bound to under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. Raz & Safra (1997) established a lower bound of, where is a constant, under the weaker assumption that PNP. A similar result with a higher value of was recently proved by Alon, Moshkovitz & Safra (2006).
Read more about this topic: Set Cover Problem
Famous quotes containing the word results:
““The ideal reasoner,” he remarked, “would, when he had once been shown a single fact in all its bearings, deduce from it not only all the chain of events which led up to it but also all the results which would follow from it.””
—Sir Arthur Conan Doyle (1859–1930)