On approximation algorithms for the terminal Steiner tree problem
Please always quote using this URN:urn:nbn:de:0296-matheon-2812
- The terminal Steiner tree problem is a special version of the Steiner tree problem, where a Steiner minimum tree has to be found in which all terminals are leaves. We prove that no polynomial time approximation algorithm for the terminal Steiner tree problem can achieve an approximation ratio less than (1 - o(1)) ln n unless NP has slightly superpolynomial time algorithms. Moreover, we present a polynomial time approximation algorithm for the metric version of this problem with a performance ratio of 2 , where denotes the best known approximation ratio for the Steiner tree problem. This improves the previously best known approximation ratio for the metric terminal Steiner tree problem of +2.
Author: | Doratha E. Drake, Stefan Hougardy |
---|---|
URN: | urn:nbn:de:0296-matheon-2812 |
Referee: | Hans Jürgen Prömel |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2005/05/11 |
Release Date: | 2005/10/31 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 275 |