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
TypeArticle accepté pour publication ou publié
Journal nameApplied Mathematics Letters
MetadataShow full item record
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 , 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 / KeywordsComplexity; Algorithms; Algorithmical approximation
Showing items related by title and author.
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