• 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 - Request a copy

Differential approximation results for the Steiner tree problem

Monnot, Jérôme; Demange, Marc; Paschos, Vangelis (2003), Differential approximation results for the Steiner tree problem, Applied Mathematics Letters, 16, 5, p. 733-739. http://dx.doi.org/10.1016/S0893-9659(03)00075-2

Type
Article accepté pour publication ou publié
Date
2003
Journal name
Applied Mathematics Letters
Volume
16
Number
5
Publisher
Elsevier
Pages
733-739
Publication identifier
http://dx.doi.org/10.1016/S0893-9659(03)00075-2
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Demange, Marc
Paschos, Vangelis
Abstract (EN)
We study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than |V N−ε for any ε ε (0, 1), where V and N are the vertex-set of the input graph and the set of terminal vertices, respectively. For the second of the Steiner tree versions considered, the one where the input graph is supposed complete and the edge distances are arbitrary, we prove that it can be differentially approximated within 1/2. For the third one defined on complete graphs with edge distances 1 or 2, we show that it is differentially approximable within 0.82. Also, extending the result of Bern and Plassmann [1], we show that the Steiner tree problem with edge lengths 1 and 2 is MaxSNP-complete even in the case where IVY less-than-or-equals, slant rINI, for any r > 0. This allows us to finally show that the Steiner tree problem with edge lengths 1 and 2 cannot by approximated by polynomial time differential approximation schemata.
Subjects / Keywords
Complexity; Algorithms; Algorithmical approximation

Related items

Showing items related by title and author.

  • Thumbnail
    Complexity and approximation results for the min weighted node coloring problem 
    Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
  • Thumbnail
    Differential approximation results for the traveling salesman problem with distances 1 and 2 
    Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié
  • Thumbnail
    Differential approximation results for the traveling salesman problem with distances 1 and 2 
    Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2001) Communication / Conférence
  • Thumbnail
    Bridging gap between standard and differential polynomial approximation: the case of bin-packing 
    Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (1999) Article accepté pour publication ou publié
  • Thumbnail
    The hypocoloring problem: complexity and approximability results when the chromatic number is small 
    de Werra, Dominique; Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
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