  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 Exponential Time Hypothesis.
This essentially matches the best upper bound known by Cygan et al.\ (IPL,
2009) of $(1-\gamma)\ln N$-factor in time $exp(O(N^\gamma))$.
  The lower bound is obtained by extracting a standalone reduction from Label
Cover to Set Cover from the work of Moshkovitz (Theory of Computing, 2015), 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-\gamma)\ln N$-approximation algorithm for these problems that runs in
$exp(\tilde{O}(N^\gamma))$ time, for any $1/2 \le \gamma < 1$.
