CSpace
 Approximation algorithms for solving the line-capacitated minimum Steiner tree problem Li, Jianping1; Wang, Wencheng1; Lichen, Junran2,3; Liu, Suding1; Pan, Pengxiang1 2022-06-06 Source Publication JOURNAL OF GLOBAL OPTIMIZATION ISSN 0925-5001 Pages 28 Abstract In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = (r(1), r(2),...,r(n)} of n terminals in R-2, a demand function d : X -> N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T-l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of TO connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight Sigma(e is an element of Tl) w(e) of such a Steiner tree T-l among all line-capacitated Steiner trees mentioned-above, where weight w(e) = 0 if two endpoints of that edge e is an element of T-l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e is an element of T-l . In addition, when this line l is as an input in R-2 and Sigma(r is an element of X) d(r) <= C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a rho(st )-approximation algorithm to solve the Euclidean minimum Steiner tree problem and a rho(1Lf)-approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (rho(st)rho(1Lf )+2)-approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r is an element of X is less than c/2, we provide a (rho(1Lf) + 2)-approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r is an element of X is at least c/2, using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem. Keyword Combinatorial optimization Locations of lines Line-capacitated Steiner trees Approximation algorithms Exact algorithms DOI 10.1007/s10898-022-01163-x Indexed By SCI Language 英语 Funding Project National Natural Science Foundation of China[11861075] ; National Natural Science Foundation of China[12101593] ; Project for Innovation Team (Cultivation) of Yunnan Province[202005AE160006] ; Key Project of Yunnan Provincial Science and Technology Department and Yunnan University[2018FY001014] ; Program for Innovative Research Team (in Science and Technology) in Universities of Yunnan Province[C176240111009] ; Project of Yunling Scholars Training of Yunnan Province ; Yunnan Provincial Department of Education Science Research Fund[2019Y0022] WOS Research Area Operations Research & Management Science ; Mathematics WOS Subject Operations Research & Management Science ; Mathematics, Applied WOS ID WOS:000806126100002 Publisher SPRINGER Citation statistics Document Type 期刊论文 Identifier http://ir.amss.ac.cn/handle/2S8OKBNM/61494 Collection 中国科学院数学与系统科学研究院 Corresponding Author Li, Jianping Affiliation 1.Yunnan Univ, Dept Math, East Outer Ring South Rd, Kunming 650504, Yunnan, Peoples R China2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, 55 Zhongguancun East Rd, Beijing 100190, Peoples R China3.Beijing Univ Chem Technol, Sch Math & Phys, 15 North Third Ring East Rd, Beijing 100029, Peoples R China Recommended CitationGB/T 7714 Li, Jianping,Wang, Wencheng,Lichen, Junran,et al. Approximation algorithms for solving the line-capacitated minimum Steiner tree problem[J]. JOURNAL OF GLOBAL OPTIMIZATION,2022:28. APA Li, Jianping,Wang, Wencheng,Lichen, Junran,Liu, Suding,&Pan, Pengxiang.(2022).Approximation algorithms for solving the line-capacitated minimum Steiner tree problem.JOURNAL OF GLOBAL OPTIMIZATION,28. MLA Li, Jianping,et al."Approximation algorithms for solving the line-capacitated minimum Steiner tree problem".JOURNAL OF GLOBAL OPTIMIZATION (2022):28.
 Files in This Item: There are no files associated with this item.
 Related Services Recommend this item Bookmark Usage statistics Export to Endnote Google Scholar Similar articles in Google Scholar [Li, Jianping]'s Articles [Wang, Wencheng]'s Articles [Lichen, Junran]'s Articles Baidu academic Similar articles in Baidu academic [Li, Jianping]'s Articles [Wang, Wencheng]'s Articles [Lichen, Junran]'s Articles Bing Scholar Similar articles in Bing Scholar [Li, Jianping]'s Articles [Wang, Wencheng]'s Articles [Lichen, Junran]'s Articles Terms of Use No data! Social Bookmark/Share