Thumbnail - No thumbnail

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é
External document link
https://hal.sorbonne-universite.fr/hal-01432021
Date
2016
Journal name
RAIRO - Operations Research
Volume
50
Number
4-5
Publisher
EDP Sciences
Pages
979-994
Publication identifier
Metadata
Show full item record
Author(s)
Escoffier, Bruno
Laboratoire 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]
Abstract (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.
Subjects / Keywords
Branching algorithm; moderately exponential approximation; approximation schema