In this paper, we address the problem of constructing a Steiner tree in the Euclidean plane $\mathbb{R}^2$ using stock pieces of materials with fixed length, which is modelled as follows. Given a set X = {r1,r2, …,rn} of n terminals in $\mathbb{R}^2$ and some stock pieces of materials with fixed length L, we are asked to construct a Steiner tree T interconnecting all terminals in X, and each edge in T must be constructed by a part of that stock piece of material. The objective is to minimize the cost of constructing such a Steiner tree T, where the cost includes three components, (1) The cost of Steiner points needed in T; (2) The construction cost of constructing all edges in T and (3) The cost of stock pieces of such materials used to construct all edges in T. We can obtain two main results. (1) Using techniques of constructing a Euclidean minimum spanning tree on the set X and a strategy of solving the bin-packing problem, we present a simple 4-approximation algorithm in time O(nlogn) to solve this new problem; (2) Using techniques of computational geometry to solve two nonlinear mathematical programming to obtain a key Lemma 8 and using other strategy of solving the binpacking problem, we design a 3-approximation algorithm in time O(n3) to resolve this new problem.
Jian-Ping Li, Wen-Cheng Wang, Jun-Ran Lichen, Yu-Jie Zheng
. Approximation Algorithms for Constructing Steiner Trees in the Euclidean Plane R2 Using Stock Pieces of Materials with Fixed Length[J]. Journal of the Operations Research Society of China, 2024
, 12(4)
: 996
-1021
.
DOI: 10.1007/s40305-022-00443-3
[1] Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM J. Appl. Math. 32(4), 835-859(1977)
[2] Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782(1998)
[3] Hwang, F.K., Richards, D.S.: Steiner tree problem. Networks 22(1), 55-89(1992)
[4] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, New York (2010)
[5] Wang, L.S., Li, Z.M.: An approximation algorithm for a bottleneck k-Steiner tree problem in the Euclidean plane. Inform. Process. Lett. 81(3), 151-156(2002)
[6] Wang, L.S., Du, D.Z.: Approximations for a bottleneck Steiner tree problem. Algorithmica 32(4), 554-561(2002)
[7] Garey,M.R., Johnson,D.S.: Computers andIntractability:AGuide to the Theory ofNP-Completeness. W. H. Freeman and Company, New York (1979)
[8] Cieslik, D.: Steiner Minimal Trees. Springer, New York (1998)
[9] Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2008)
[10] Rubinstein, J.H., Thomas, D.A., Weng, J.F.: Degree-five Steiner points cannot reduce network costs for planar sets. Networks 22(6), 531-537(1992)
[11] Remy, J., Steger, A.: Approximation schemes for node-weighted geometric Steiner tree problems. Algorithmica 55(1), 240-267(2009)
[12] Brazil, B., Zachariasen, M.: Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications. Springer, Switzerland (2015)
[13] Segev, A.: The node-weighted Steiner tree problem. Networks 17(1), 1-17(1987)
[14] Sarrafzadeh, M., Wong, C.K.: Bottleneck Steiner trees in the plane. IEEE Trans. Comput. 41(3), 370-374(1992)
[15] Ramamurthy, B., Iness, J., Mukherjee, B.: Minimizing the number of optical amplifiers needed to support a multi-wavelength optical lan/man. In: In: Proceedings of IEEE Comput. Soc. Press INFOCOM ’97, Vol 1, pp. 261-268(1997)
[16] Lin, G.H., Xue, G.: Steiner tree problem with minimum number of Steiner points and bounded edgelength. Inform. Process. Lett. 69(2), 53-57(1999)
[17] Chen, D.H., Du, D.Z., Hu, X.D., Lin, G.H., Wang, L.S., Xue, G.L.: Approximations for Steiner trees with minimum number of Steiner points. J. Glob. Optim. 262(1), 17-33(2000)
[18] Li, J., Wang, H., Huang, B., LiChen, J.: Approximations for two variants of the Steiner tree problem in the Euclidean plane R2. J. Glob. Optim. 57(3), 783-801(2013)
[19] Chung, F.R.K., Graham, R.L.: A new bound for Euclidean Steiner minimal trees. Ann. NY. Acad. Sci. 440(1), 328-346(1985)
[20] Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, New York (2008)
[21] Papadimitriou, C.H., Steiglitz, D.K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, New Jersey (1998)
[22] Shamos, M.I., Hoey, D.: Closest-point problems. In: The 16th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, pp. 151-162(1975)
[23] Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, London (2008)
[24] Du, D., Wang, L., Xu, B.: The Euclidean bottleneck Steiner tree and Steiner tree with minimum number of Steiner points. In: Computing and Combinatorics, 7th Annual International Conference, COCOON 2001, pp. 509-518(2001)
