
Exponential approximation schemata for some network design problems
Boria, Nicolas; Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2013), Exponential approximation schemata for some network design problems, Journal of Discrete Algorithms, 22, p. 43-52. 10.1016/j.jda.2013.06.011
View/ Open
Type
Article accepté pour publication ou publiéDate
2013Journal name
Journal of Discrete AlgorithmsVolume
22Publisher
Elsevier
Pages
43-52
Publication identifier
Metadata
Show full item recordAuthor(s)
Boria, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Bourgeois, Nicolas
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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]
Abstract (EN)
We 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.Subjects / Keywords
Exponential algorithms; Approximation algorithms; Traveling Salesman Problem; Steiner treeRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Article accepté pour publication ou publié