Show simple item record

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBoria, Nicolas
HAL ID: 21013
ORCID: 0000-0002-0548-4257
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorBourgeois, Nicolas*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis*
dc.date.accessioned2011-05-19T12:57:58Z
dc.date.available2011-05-19T12:57:58Z
dc.date.issued2013
dc.identifier.issn1570-8667
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6302
dc.language.isoenen
dc.subjectExponential algorithms
dc.subjectApproximation algorithms
dc.subjectTraveling Salesman Problem
dc.subjectSteiner tree
dc.subject.ddc003en
dc.titleExponential approximation schemata for some network design problems
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study approximation of some well-known network design problems such as traveling salesman problem (for both minimization and maximization versions) and min steiner tree, by moderately exponential algorithms. The general goal of the issue of moderately exponential approximationis to catch-up on polynomial inapproximability, by providing algorithms achieving, with worst-caserunning times importantly smaller than those needed for exact computation, approximation ratiosunachievable in polynomial time.
dc.relation.isversionofjnlnameJournal of Discrete Algorithms
dc.relation.isversionofjnlvol22
dc.relation.isversionofjnldate2013
dc.relation.isversionofjnlpages43-52
dc.relation.isversionofdoi10.1016/j.jda.2013.06.011
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevier
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-21T08:17:40Z
hal.identifierhal-01509539*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record