Abstract
In this paper, we consider the 1-line Euclidean minimum Steiner tree problem, which is a variation of the Euclidean minimum Steiner tree problem and defined as follows. Given a set \(P=\{r_1,r_2,\ldots , r_n\}\) of n points in the Euclidean plane \(\mathbb {R}^2\), we are asked to find the location of a line l and an Euclidean Steiner tree T(l) in \(\mathbb {R}^2\) such that at least one Steiner point is located at such a line l, the objective is to minimize total weight of such an Euclidean Steiner tree T(l), i.e., \(\min \{\sum _{e\in T(l)} w(e)~|~T(l)\) is an Euclidean Steiner tree as mentioned-above\(\}\), where we define weight \(w(e)=0\) if the end-points u, v of each edge \(e=uv \in T(l)\) are both located at such a line l and otherwise we denote weight w(e) to be the Euclidean distance between u and v. Given a fixed line l as an input in \(\mathbb {R}^2\), we refer this problem as the 1-line-fixed Euclidean minimum Steiner tree problem; In addition, when Steiner points added are all located at such a fixed line l, we refer this problem as the constrained Euclidean minimum Steiner tree problem. We obtain the following two main results. (1) Using a polynomial-time exact algorithm to find a constrained Euclidean minimum Steiner tree, we can design a 1.214-approximation algorithm to solve the 1-line-fixed Euclidean minimum Steiner tree problem, and this algorithm runs in time \(O(n\log n)\); (2) Using a combination of the algorithm designed in (1) for many times, a technique of finding linear facility location and an important lemma proved by some techniques of computational geometry, we can provide a 1.214-approximation algorithm to solve the 1-line Euclidean minimum Steiner tree problem, and this new algorithm runs in time \(O(n^3\log n)\).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aazami A, Cheriyan J, Jampani KR (2012) Approximation algorithms and hardness results for packing element-disjoint Steiner trees in planar graphs. Algorithmica 63(1–2):425–456
Arora S (1998) Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J ACM 45(5):753–782
Berg Md, Cheong O, Mv Kreveld, Overmars M (2008) Computational geometry: algorithms and applications. Springer, Berlin
Bern M, Plassmann P (1989) The Steiner problem with edge lengths 1 and 2. Inf Process Lett 32(4):171–176
Byrka J, Grandoni F, Rothvoß T, Sanità L (2010) An improved LP-based approximation for Steiner tree. In: Proceedings of the 2010 ACM international symposium on theory of computing. ACM, New York, pp 583–592
Chen G, Zhang G (2000) A constrained minimum spanning tree problem. Comput Oper Res 27(9):867–875
Chung FR, Graham RL (1982) A new bound for Euclidean Steiner minimal trees. Ann N Y Acad Sci 440(1):328–346
Cieslik D (1998) Steiner minimal trees. Kluwer Academic Publishers, Dordrecht
Garey MR, Graham RL, Johnson DS (1977) The complexity of computing Steiner minimal trees. SIAM J Appl Math 32(4):835–859
Gilbert EN, Pollak HO (1968) Steiner minimal trees. SIAM J Appl Math 16(1):1–29
Holby J (2017) Variations on the Euclidean Steiner tree problem and algorithms. Rose-Hulman Undergrad Math J 18(1):123–155
Hwang FK, Richards DS (1992) Steiner tree problems. Networks 22(1):55–89
Korte B, Vygen J (2008) Combinatorial optimization: theory and algorithms. Springer, Berlin
Kruskal JB (1956) On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc 7(1):48–50
Mitchell JS (1999) Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric tsp, k-MST, and related problems. SIAM J Comput 28(4):1298–1309
Morris JG, Norback JP (1980) A simple approach to linear facility location. Transp Sci 14(1):1–8
Rao SB, Smith WD (1999) Approximating geometrical graphs via “spanners” and “banyans”. In: STOC’98, Dallas, TX, pp 540–550
Robins G, Zelikovsky A (2005) Tighter bounds for graph Steiner tree approximation. SIAM J Discrete Math 19(1):122–134
Schrijver A (2003) Combinatorial optimization: polyhedra and efficiency. In: Algorithms and combinatorics. Springer, Berlin
Shamos MI, Hoey D (1975) Closest-point problems. In: The 16th annual symposium on foundations of computer science. IEEE Computer Society, pp 151–162
Vazirani VV (2001) Approximation algorithms. Springer, Berlin
Williamson DP, Shmoys DB (2011) The design of approximation algorithms. Cambridge University Press, Cambridge
Acknowledgements
The authors are indeed grateful to the two anonymous reviewers whose kind suggestions and comments have led to a substantially improved presentation for this manuscript. These authors are supported by the fund from the National Natural Science Foundation of China [No.11861075], Project for Innovation Team Project (Cultivation) of Yunnan Province, IRTSTYN, Key Project of Yunnan Provincial Science and Technology Department and Yunnan University [No. 2018FY001(-014)]. Junran Lichen is supported by the fund from the China Scholarship Council (No.201807030001).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Li, J., Liu, S., Lichen, J. et al. Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem. J Comb Optim 39, 492–508 (2020). https://doi.org/10.1007/s10878-019-00492-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-019-00492-0