Tight Bounds on Subexponential Time Approximation of Set Cover and Related Problems

Marek Cygan, Magnús M. Halldórsson, Guy Kortsarz

We show that Set Cover on instances with $N$ elements cannot be approximated within $(1-\gamma )\ln N$-factor in time exp($N^{\gamma -\delta })$, for any $0<\gamma <1$ and any $\delta >0$, assuming the Expo…