Approximation algorithms for solving the 1-line Euclidean minimum Steiner tree problem

Jianping Li (), Suding Liu (), Junran Lichen (), Wencheng Wang () and Yujie Zheng ()
Additional contact information
Jianping Li: Yunnan University
Suding Liu: Yunnan University
Junran Lichen: Yunnan University
Wencheng Wang: Yunnan University
Yujie Zheng: Yunnan University

Journal of Combinatorial Optimization, 2020, vol. 39, issue 2, No 11, 492-508

Abstract: 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\}$$P={r1,r2,…,rn} of n points in the Euclidean plane $$\mathbb {R}^2$$R2, we are asked to find the location of a line l and an Euclidean Steiner tree T(l) in $$\mathbb {R}^2$$R2 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)$$min{∑e∈T(l)w(e)|T(l) is an Euclidean Steiner tree as mentioned-above$$\}$$}, where we define weight $$w(e)=0$$w(e)=0 if the end-points u, v of each edge $$e=uv \in T(l)$$e=uv∈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$$R2, 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)$$O(nlogn); (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)$$O(n3logn).

Keywords: 1-Line Euclidean minimum Steiner tree; Constrained Euclidean minimum Steiner tree; Steiner ratio; Approximation algorithms; Complexity (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00492-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:39:y:2020:i:2:d:10.1007_s10878-019-00492-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00492-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().