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:
“Pain itself can be pleasurable accidentally in so far as it is accompanied by wonder, as in stage-plays; or in so far as it recalls a beloved object to one’s memory, and makes one feel one’s love for the thing, whose absence gives us pain. Consequently, since love is pleasant, both pain and whatever else results from love, in so far as they remind us of our love, are pleasant.”
—Thomas Aquinas (c. 1225–1274)