Super-polynomial approximation branching algorithms
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2016), Super-polynomial approximation branching algorithms, RAIRO - Operations Research, 50, 4-5, p. 979-994. 10.1051/ro/2015060
Type
Article accepté pour publication ou publiéLien vers un document non conservé dans cette base
https://hal.sorbonne-universite.fr/hal-01432021Date
2016Nom de la revue
RAIRO - Operations ResearchVolume
50Numéro
4-5Éditeur
EDP Sciences
Pages
979-994
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Escoffier, BrunoLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 ± ϵ, for arbitrarily small ϵ) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.Mots-clés
Branching algorithm; moderately exponential approximation; approximation schemaPublications associées
Affichage des éléments liés par titre et auteur.
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Communication / Conférence
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2015) Article accepté pour publication ou publié
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper