Abstract
Given n terminals in the Euclidean plane and a positive constant, find a Steiner tree interconnecting all terminals with the minimum number of Steiner points such that the Euclidean length of each edge is no more than the given positive constant. This problem is NP-hard with applications in VLSI design, WDM optical networks and wireless communications. In this paper, we show that (a) the Steiner ratio is 1/ 4, that is, the minimum spanning tree yields a polynomial-time approximation with performance ratio exactly 4, (b) there exists a polynomial-time approximation with performance ratio 3, and (c) there exists a polynomial-time approxi-mation scheme under certain conditions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Arora, S. (1996), Polynomial time approximation schemes for Euclidean TSP and other geometric problems, Proceedings of 37th FOCS.
Chiang, C., Sarrafzadeh, M. and Wong, C.K. (1990), A powerful global router: based on Steiner min-max tree, in Proc. ICCAD-89; also IEEE Transactions on Computer-Aided Design 19: 1318–1325.
Du, D.-Z. and Hwang, F.K. (1992), A proof of Gilbert-Pollak's conjecture on the Steiner ratio, Algorithmica 7: 121-135.
Hochbaum, D.S. and Maass, W. (1985), Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM 32: 130-136.
Hwang, F.K. and Richards, D.S. (1992), Steiner tree problems, Networks 22: 55-89.
Garey, M.R. Graham, R.L. and Johnson, D.S. (1977), The complexity of computing Steiner minimal trees, SIAM Journal on Applied Mathematics 32: 835-859.
Gilbert, E.N. (1967), Minimum cost communication networks, Bell System Technical Journal 9: 2209-2227.
Gilbert, E.N. and Pollak, H.O. (1968), Steiner minimal trees, SIAM Journal on Applied Mathematics 16: 1-29.
Hwang, F.K., Richard, D. and Winter, P. (1992), The Steiner minimum tree problems, Annals of Discrete Mathematics, Vol. 53, North-Holland.
Karpinski, M. and Zelikovsky, A. (1997), New approximation algorithms for the Steiner tree problems, Journal of Combinatorial Optimization 1(1): 47-65.
Li, C.-S., Tong, F.F., Georgiou, C.J. and Chen, M., Gain equalization in metropolitan and wide area optical networks using optical amplifiers, Proc. IEEE INFOCOM' 94, pp. 130-137, June 1994.
Lin, G.-H. and Xue, G.L. (1999), Steiner tree problem with minimum number of Steiner points and bounded edge-length, Information Processing Letters 69: 53-57.
Rubinstein, J.L. and Weng, J.F. (1997), Compression theorems and Steiner ratios on spheres, Journal of Combinatorial Optimization 1(1): 67-78.
Ramamurthy, B., Iness, J. and Mukherjee, B., Minimizing the number of optical amplifiers needed to support a multi-wavelength optical LAN/MAN, Proc. IEEE INFO-COM' 97, pp. 261-268, April 1997.
Soukup, J. (1975), On minimum cost network with nonlinear costs, SIAM Journal on Computing 29: 571-581.
Wang, L. and Jiang, T. (1996), An approximation scheme for some Steiner tree problems in the plane, Networks 28: 187-193.
West, D.B. (1996), Introduction to Graph Theory, Prentice Hall.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
CHEN, D., DU, DZ., HU, XD. et al. Approximations for Steiner Trees with Minimum Number of Steiner Points. Journal of Global Optimization 18, 17–33 (2000). https://doi.org/10.1023/A:1008384012064
Issue Date:
DOI: https://doi.org/10.1023/A:1008384012064