Set Cover Problem - Inapproximability Results

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:

    A distinction of property results from that very protection which a free Government gives to unequal faculties of acquiring it.
    James Madison (1751–1836)