  In this paper we focus on problems which do not admit a constant-factor
approximation in polynomial time and explore how quickly their approximability
improves as the allowed running time is gradually increased from polynomial to
(sub-)exponential.
  We tackle a number of problems: For Min Independent Dominating Set, Max
Induced Path, Forest and Tree, for any $r(n)$, a simple, known scheme gives an
approximation ratio of $r$ in time roughly $r^{n/r}$. We show that, for most
values of $r$, if this running time could be significantly improved the ETH
would fail. For Max Minimal Vertex Cover we give a non-trivial
$\sqrt{r}$-approximation in time $2^{n/r}$. We match this with a similarly
tight result. We also give a $\log r$-approximation for Min ATSP in time
$2^{n/r}$ and an $r$-approximation for Max Grundy Coloring in time $r^{n/r}$.
  Furthermore, we show that Min Set Cover exhibits a curious behavior in this
super-polynomial setting: for any $\delta > 0$ it admits an
$m^\delta$-approximation, where $m$ is the number of sets, in just
quasi-polynomial time. We observe that if such ratios could be achieved in
polynomial time, the ETH or the Projection Games Conjecture would fail.
