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

We show that Set-Cover on instances with N elements cannot be approximated within (1 - γ) ln N -factor in time exp(N^{γ - δ}), for any 0 < γ< 1 and any δ> 0, assuming the Exponential Time Hypothesis. This essentially matches the best upper bound known by Cygan, Kowalik, and Wykurz [6] of (1 - γ) ln N -factor in time exp(O(N^γ) ). The lower bound is obtained by extracting a standalone reduction from Label-Cover to Set-Cover from the work of Moshkovitz [18], and applying it to a different PCP theorem than done there. We also obtain a tighter lower bound when conditioning on the Projection Games Conjecture. We also treat three problems (Directed Steiner Tree, Submodular Cover, and Connected Polymatroid) that strictly generalize Set-Cover. We give a (1 - γ) ln N -approximation algorithm for these problems that runs in exp(O~ (N^γ) ) time, for any 1 / 2 ≤ γ< 1.