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
2003Journal name
Applied Mathematics LettersVolume
16Number
5Publisher
Elsevier
Pages
733-739
Publication identifier
Metadata
Show full item recordAbstract (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 approximationRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Toulouse, Sophie; Paschos, Vangelis; Monnot, Jérôme (2003) Article accepté pour publication ou publié
-
Monnot, Jérôme; Paschos, Vangelis; Toulouse, Sophie (2001) Communication / Conférence
-
Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (1999) Article accepté pour publication ou publié
-
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