Show simple item record

Moderately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximation

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2013-01-08T16:02:05Z
dc.date.available2013-01-08T16:02:05Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/10799
dc.language.isoenen
dc.subjectNP-hard problemsen
dc.subjectpolynomial approximationen
dc.subject.ddc003en
dc.titleModerately Exponential Approximation: Bridging the Gap Between Exact Computation and Polynomial Approximationen
dc.typeCommunication / Conférence
dc.description.abstractenThis paper proposes a way to bring together two seemingly “foreign” domains that are the polynomial approximation and the exact computation for NP-hard problems. We show how one can match ideas from both areas in order to design approximation algorithms achieving ratios unachievable in polynomial time (unless a very unlikely complexity conjecture is confirmed) with worst-case complexity much lower (though super-polynomial) than that of an exact computation.en
dc.identifier.citationpages1-14en
dc.relation.ispartofseriestitleSpringer Proceedings in Mathematics & Statisticsen
dc.relation.ispartofseriesnumbervol 31en
dc.relation.ispartoftitleOptimization Theory, Decision Making, and Operations Research Applicationsen
dc.relation.ispartofeditorMigdalas, Athanasios
dc.relation.ispartofeditorSifaleras, Angelo
dc.relation.ispartofeditorGeorgiadis, Christos K.
dc.relation.ispartofeditorPapathanasiou, Jason
dc.relation.ispartofeditorStiakakis, Emmanuil
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2013
dc.relation.ispartofpages359en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-1-4614-5134-1en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-1-4614-5133-4en
dc.relation.conftitle1st International Symposium and 10th Balkan Conference on Operational Research (BALCOR 2011)en
dc.relation.confdate2011-09
dc.relation.confcityThessaloniqueen
dc.relation.confcountryGreeceen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.identifier.doi10.1007/978-1-4614-5134-1_1en
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01511873*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut


Files in this item

Thumbnail
Name:
presentation_1.pdf
Size:
690.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record