Editing Set cover problem (section)

== Inapproximability results ==

When <math> n</math> refers to the size of the universe, {{harvtxt |Lund|Yannakakis|1994}} showed that set covering cannot be approximated in polynomial time to within a factor of <math>\tfrac{1}{2}\log_2{n} \approx 0.72\ln{n}</math>, unless '''NP''' has [[quasi-polynomial time]] algorithms. [[Uriel Feige|Feige]] (1998) improved this lower bound to <math>\bigl(1-o(1)\bigr)\cdot\ln{n}</math> under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. {{harvtxt |Raz|Safra|1997}} established a lower bound
of <math>c\cdot\ln{n}</math>, where <math>c</math> is a certain constant, under the weaker assumption that '''P'''<math>\not=</math>'''NP'''.
A similar result with a higher value of <math>c</math> was recently proved by {{harvtxt |Alon|Moshkovitz|Safra|2006}}. {{harvtxt |Dinur|Steurer|2013}} showed optimal inapproximability by proving that it cannot be approximated to <math>\bigl(1 - o(1)\bigr) \cdot \ln{n}</math> unless '''P'''<math>=</math>'''NP'''.

In low-frequency systems, {{harvtxt |Dinur|Guruswami|Khot|Regev|2003}} proved it is NP-hard to approximate set cover to better than <math>f-1-\epsilon</math>.
If the [[Unique games conjecture]] is true, this can be improved to <math>f-\epsilon</math> as proven by {{harvtxt |Khot|Regev|2008}}.

{{harvtxt |Trevisan|2001}} proves that set cover instances with sets of size at most <math>\Delta</math> cannot be approximated to a factor better than <math>\ln \Delta - O(\ln \ln \Delta)</math> unless '''P'''<math>=</math>'''NP''', thus making the approximation of <math>\ln \Delta + 1</math> of the greedy algorithm essentially tight in this case.