Time-approximation trade-offs for inapproximable problems

• Published in: Journal of computer and system sciences 2018-03, Vol.92, p.171-180
• Main Authors: Bonnet, Édouard, Lampis, Michael, Paschos, Vangelis Th
• Format: Article
• Language: English
• Subjects: Approximation algorithms; Computational Complexity; Computer Science; Data Structures and Algorithms; Exponential algorithms; Hardness of approximation; Sub-exponential algorithms
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2017.09.009

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. •Some problems are very hard to approximate in polynomial time.•We consider these problems in the context of sub-exponential time.•We give (often tight) trade-offs between time and approximation.