Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2017-11-07T16:45:54Z
dc.date.available2017-11-07T16:45:54Z
dc.date.issued2015
dc.identifier.issn1619-4500
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16930
dc.language.isoenen
dc.subjectComplexityen
dc.subjectPolynomial approximationen
dc.subjectExact algorithmen
dc.subjectModerately exponential approximationen
dc.subject.ddc003en
dc.titleWhen polynomial approximation meets exact computationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe outline a relatively new research agenda aiming at building a new approximation paradigm by matching two distinct domains, the polynomial approximation and the exact solution of NP -hard problems by algorithms with guaranteed and non-trivial upper complexity bounds. We show how one can design approximation algorithms achieving ratios that are “forbidden” in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower than that of an exact computation.en
dc.relation.isversionofjnlname4OR
dc.relation.isversionofjnlvol13en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2015-09
dc.relation.isversionofjnlpages227-245en
dc.relation.isversionofdoi10.1007/s10288-015-0294-7en
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
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.updated2017-10-27T16:57:19Z
hal.identifierhal-01630567*
hal.version1*
hal.update.actionupdateMetadata*
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