Time-approximation trade-offs for inapproximable problems

In this paper we focus on problems inapproximable 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 rn/r. We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a r-approximation in time 2n/r. We match this with a similarly tight result. We also give a log⁡r-approximation for Min ATSP in time 2n/r and an r-approximation for Max Grundy Coloring in time rn/r. Finally, we investigate the approximability of Min Set Cover, when measuring the running time as a function of the number of sets in the input.