Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem

doi:10.1007/s40305-022-00437-1

Journal of the Operations Research Society of China ›› 2024, Vol. 12 ›› Issue (3): 729-755.doi: 10.1007/s40305-022-00437-1

Previous Articles Next Articles

Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem

Jian-Ping Li¹, Su-Ding Liu¹, Jun-Ran Lichen², Peng-Xiang Pan¹, Wen-Cheng Wang¹

1 Department of Mathematics, Yunnan University, Kunming 650504, Yunnan, China;
2 School of Mathematics and Physics, Beijing University of Chemical Technology, Beijing 650504, China

Received:2021-11-20 Revised:2022-06-02 Online:2024-09-30 Published:2024-08-15
Contact: Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang E-mail:jianping@ynu.edu.cn;suding2020@163.com;J.R.Lichen@buct.edu.cn;pengxiang@ynu.edu.cn;wencheng2018a@163.com
Supported by:
This paper is supported by the National Natural Science Foundation of China (Nos. 11861075 and 12101593), Project for Innovation Team (Cultivation) of Yunnan Province (No. 202005AE160006), Key Project of Yunnan Provincial Science and Technology Department and Yunnan University (No. 2018FY001014) and Program for Innovative Research Team (in Science and Technology) in Universities of Yunnan Province (No. C176240111009). Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province. Su-Ding Liu is also supported by the Graduate Research and Innovation Project of Yunnan University (No. 2020Z66).

Abstract

Abstract: We address the 1-line minimum Steiner tree of line segments (1L-MStT-LS) problem. Specifically, given a set S of n disjoint line segments in $\mathbb{R}^2$, we are asked to find the location of a line l and a set E_l of necessary line segments (i.e., edges) such that a graph consisting of all line segments in S ∪ E_l plus this line l, denoted by T_l = (S, l, E_l), becomes a Steiner tree, the objective is to minimize total length of edges in El among all such Steiner trees. Similarly, we are asked to find a set E₀ of necessary edges such that a graph consisting of all line segments in S ∪ E₀, denoted by T_S = (S, E₀), becomes a Steiner tree, the objective is to minimize total length of edges in E₀ among all such Steiner trees, we refer to this new problem as the minimum Steiner tree of line segments (MStT-LS) problem. In addition, when two endpoints of each edge in E₀ need to be located on two different line segments in S, respectively, we refer to that problem as the minimum spanning tree of line segments (MST-LS) problem. We obtain three main results: (1) Using technique of Voronoi diagram of line segments, we design an exact algorithm in time O(nlogn) to solve the MST-LS problem; (2) we show that the algorithm designed in (1) is a 1.214-approximation algorithm to solve the MStT-LS problem; (3) using the combination of the algorithm designed in (1) as a subroutine for many times, a technique of finding linear facility location and a key lemma proved by techniques of computational geometry, we present a 1.214-approximation algorithm in time O(n³logn) to solve the 1L-MStT-LS problem.

Key words: 1-Line minimum Steiner tree of line segments, Minimum spanning tree of line segments, Voronoi diagram of line segments, Steiner ratio, Approximation algorithms

CLC Number:

90C27
68U05

Jian-Ping Li, Su-Ding Liu, Jun-Ran Lichen, Peng-Xiang Pan, Wen-Cheng Wang. Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem[J]. Journal of the Operations Research Society of China, 2024, 12(3): 729-755.

TrendMD

References

[1] Kruskal, J.B.: On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48-50(1956)
[2] Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms. Springer, Berlin (2008)
[3] Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Berlin (2003)
[4] Chazelle, B.: A minimum spanning tree algorithm with inverse-Ackermann type complexity. J. ACM 47(6), 1028-1047(2000)
[5] Pettie, S., Ramachandran, V.: An optimal minimum spanning tree algorithm. J. ACM 49(1), 16-34(2002)
[6] Cheriton, D., Tarjan, R.E.: Finding minimum spanning trees. SIAM J. Comput. 5(4), 724-742(1976)
[7] Shamos, M.I., Hoey, D.: Closest-point problems. In: 16th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Long Beach, Calif, pp. 151-162(1975)
[8] Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, New York (2008)
[9] Bose, P., Toussaint, G.: Growing a tree from its branches. J. Algorithms 19(1), 86-103(1995)
[10] Borgelt, M.G., van Kreveld, M., Löffler, M., Luo, J., Merrick, D., Silveira, R.I., Vahedi, M.: Planar bichromatic minimum spanning trees. J. Discrete Algorithms 7(4), 469-478(2009)
[11] Dey, S., Jallu, R.K., Nandy, S.C.: Minimum spanning tree of line segments. Lect. Not. Comput. Sci. 10976, 529-541(2018)
[12] Chen, G., Zhang, G.: A constrained minimum spanning tree problem. Comput. Oper. Res. 27(9), 867-875(2000)
[13] Aazami, A., Cheriyan, J., Jampani, K.R.: Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs. Algorithmica 63(1-2), 425-456(2012)
[14] Ljubić, I.: Solving Steiner trees: recent advances, challenges, and perspectives. Networks 77(2), 177- 204(2020)
[15] Hwang, F.K., Richards, D.S.: Steiner tree problems. Networks 22(1), 55-89(1992)
[16] Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms. Cambridge University Press, Cambridge (2011)
[17] Robins, G., Zelikovsky, A.: Tighter bounds for graph Steiner tree approximation. SIAM J. Discrete Math. 19, 122-134(2005)
[18] Byrka, J., Grandoni, F., Rothvoß, T., Sanità, L.: Steiner tree approximation via iterative randomized rounding. J. ACM 60(1), 1-33(2013)
[19] 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)
[20] Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753-782(1998)
[21] Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomialtime approximation scheme for geometric TSP, k-MStT, and related problems. SIAM J. Comput. 28, 1298-1309(1999)
[22] Rao, S.B., Smith, W.D.: Approximating geometrical graphs via “panners” and “banyans”. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, New York, pp. 540-550(1999)
[23] Cieslik, D.: Steiner Minimal Trees. Kluwer Academic Publishers, Dordrecht (1998)
[24] Vazirani, V.V.: Approximation Algorithms. Springer, Berlin (2001)
[25] Holby, J.: Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad. Math. J. 18(1), 123-155(2017)
[26] Li, J., Liu, S., Lichen, J., Wang, W., Zheng, Y.: Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J. Comb. Optim. 39, 492-508(2020)
[27] Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1-29(1968)
[28] Chung, F., Graham, R.L.: A new bound for Euclidean Steiner minimal trees. Ann. N. Y. Acad. Sci. 440(1), 328-346(1985)
[29] Megiddo, N., Tamir, A.: Finding least-distances lines. SIAM J. Algebraic Discrete Methods 4, 207-211(1981)
[30] Althaus, E., Rauterberg, F., Ziegler, S.: Computing Euclidean Steiner trees over segments. EURO J. Comput. Optim. 8, 309-325(2020)
[31] Juhl, D., Warme, D.M., Winter, P., Zachariasen, M.: The Geosteiner software package for computing Steiner trees in the plane: an updated computational study. Math. Program. Comput. 10, 487-532(2018)

Approximation Algorithms for Solving the 1-Line Minimum Steiner Tree of Line Segments Problem

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Correlation Clustering [J]. Journal of the Operations Research Society of China, 2023, 11(4): 911-924.
[2]	Zhong-Zheng Tang, Zhuo Diao. Approximation Algorithms on k-Cycle Transversal and k-Clique Transversal [J]. Journal of the Operations Research Society of China, 2021, 9(4): 883-892.
[3]	Jian Li· Yu Liu. Approximation Algorithms for Stochastic Combinatorial Optimization Problems [J]. Journal of the Operations Research Society of China, 2016, 4(1): 1-.