Show simple item record

dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorTourniaire, Emeric
dc.date.accessioned2013-11-22T13:15:07Z
dc.date.available2013-11-22T13:15:07Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/12146
dc.language.isoenen
dc.subjectComplexité
dc.subjectAlgorithme et structure de données
dc.subject.ddc003en
dc.titleModerate exponential time approximation and branching algorithms
dc.typeDocument de travail / Working paper
dc.description.abstractenWe study links between approximation, exponential time computation and fixed parameter tractability. In particular, rather than focusing on one particular optimization problem, we tackle the question of finding sufficient conditions for a problem to admit "good" approximation algorithms in exponential time. In particular, we focus on the existence of "approximation schemata" (ratios 1 ± ε for arbitrarily small ε) and we exhibit conditions under which a technique of devising approximate branching algorithms reaches interesting results.
dc.publisher.nameUniversité Paris-Dauphine
dc.publisher.cityParisen
dc.identifier.citationpages16
dc.relation.ispartofseriestitleCahiers du Lamsade
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00874358
dc.subject.ddclabelRecherche opérationnelleen
dc.description.submittednonen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-02-09T16:19:11Z


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