Show simple item record

dc.contributor.authorBonnet, Édouard*
dc.contributor.authorLampis, Michael*
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2017-03-14T13:17:54Z
dc.date.available2017-03-14T13:17:54Z
dc.date.issued2016
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16336
dc.language.isoenen
dc.subjectApproximationen
dc.subjectComplexityen
dc.subjectPolynomial and Subexponential Approximationen
dc.subjectReductionen
dc.subjectInapproximabilityen
dc.subject.ddc003en
dc.titleTime-Approximation Trade-offs for Inapproximable Problemsen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages22:1-22:14en
dc.relation.ispartoftitle33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)en
dc.relation.ispartofeditorOllinger, Nicolas
dc.relation.ispartofeditorVollmer, Heribert
dc.relation.ispartofpublnameSchloss Dagstuhl--Leibniz-Zentrum fuer Informatiken
dc.relation.ispartofpublcityWadernen
dc.relation.ispartofdate2016-02
dc.relation.ispartofpages798en
dc.relation.ispartofurl10.4230/LIPIcs.STACS.2016.0en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-95977-001-9en
dc.relation.conftitle33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)en
dc.relation.confdate2016-02
dc.relation.confcityOrléansen
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.4230/LIPIcs.STACS.2016.22en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-03-14T12:56:03Z
hal.person.labIds220549*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01489450*
hal.faultCodeThe supplied format packaging is not supported by the server


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record