Moderate exponential time approximation and branching algorithms
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012), Moderate exponential time approximation and branching algorithms. https://basepub.dauphine.fr/handle/123456789/12146
Type
Document de travail / Working paperExternal document link
https://hal.archives-ouvertes.fr/hal-00874358Date
2012Publisher
Université Paris-Dauphine
Series title
Cahiers du LamsadePublished in
Paris
Pages
16
Metadata
Show full item recordAbstract (EN)
We 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.Subjects / Keywords
Complexité; Algorithme et structure de donnéesRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2016) Article accepté pour publication ou publié
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper