Show simple item record

Time-approximation trade-offs for inapproximable problems

hal.structure.identifier
dc.contributor.authorBonnet, Édouard
HAL ID: 171728
ORCID: 0000-0002-1653-5822		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorLampis, Michael
HAL ID: 182546
ORCID: 0000-0002-5791-0887		*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2019-07-02T10:09:36Z
dc.date.available2019-07-02T10:09:36Z
dc.date.issued2018
dc.identifier.issn0022-0000
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/19104
dc.language.isoenen
dc.subjectApproximation algorithmsen
dc.subjectExponential algorithmsen
dc.subjectSub-exponential algorithmsen
dc.subjectHardness of approximationen
dc.subject.ddc005en
dc.titleTime-approximation trade-offs for inapproximable problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn 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 , a simple, known scheme gives an approximation ratio of r in time roughly . We show that, if this running time could be significantly improved, the ETH would fail. For Max Minimal Vertex Cover we give a -approximation in time . We match this with a similarly tight result. We also give a -approximation for Min ATSP in time and an r-approximation for Max Grundy Coloring in time . 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.en
dc.relation.isversionofjnlnameJournal of Computer and System Sciences
dc.relation.isversionofjnlvol92en
dc.relation.isversionofjnldate2018-03
dc.relation.isversionofjnlpages171-180en
dc.relation.isversionofdoi10.1016/j.jcss.2017.09.009en
dc.identifier.urlsitehttps://arxiv.org/abs/1502.05828v1en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2019-03-29T18:22:58Z
hal.identifierhal-02170681*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


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