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:
“Nothing is as difficult as to achieve results in this world if one is filled full of great tolerance and the milk of human kindness. The person who achieves must generally be a one-ideaed individual, concentrated entirely on that one idea, and ruthless in his aspect toward other men and other ideas.”
—Corinne Roosevelt Robinson (1861–1933)