2026-07-22T20:50:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5723 2024-03-06T10:36:56Z ddc:004 open_access

Time-Approximation Trade-offs for Inapproximable Problems Bonnet, Édouard Lampis, Michael Paschos, Vangelis Th. Algorithm Complexity Polynomial and Subexponential Approximation Reduction Inapproximability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Michael Lampis and Vangelis Th. Paschos 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.22 urn:nbn:de:0030-drops-57236 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode