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:
“For every life and every act
Consequence of good and evil can be shown
And as in time results of many deeds are blended
So good and evil in the end become confounded.”
—T.S. (Thomas Stearns)