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 peace conference must not adjourn without the establishment of some ordered system of international government, backed by power enough to give authority to its decrees. ... Unless a league something like this results at our peace conference, we shall merely drop back into armed hostility and international anarchy. The war will have been fought in vain ...”
—Virginia Crocheron Gildersleeve (1877–1965)