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:

    It is perhaps the principal admirableness of the Gothic schools of architecture, that they receive the results of the labour of inferior minds; and out of fragments full of imperfection ... raise up a stately and unaccusable whole.
    John Ruskin (1819–1900)