• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

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
cahier303.PDF (258.3Kb)
Type
Article accepté pour publication ou publié
Date
2013
Journal name
Journal of Discrete Algorithms
Volume
22
Publisher
Elsevier
Pages
43-52
Publication identifier
10.1016/j.jda.2013.06.011
Metadata
Show full item record
Author(s)
Boria, Nicolas cc
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 tree

Related items

Showing items related by title and author.

  • Thumbnail
    Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence
  • Thumbnail
    Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
  • Thumbnail
    An Introduction to Exponential Time Exact Algorithms for Solving NP-hard Problems 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2011) Chapitre d'ouvrage
  • Thumbnail
    Efficient approximation of MIN SET COVER by moderately exponential algorithms 
    Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
  • Thumbnail
    Approximation of MIN COLORING by moderately exponential algorithms 
    Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo