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 PublicationJOURNAL OF GLOBAL OPTIMIZATION
ISSN0925-5001
Pages28
AbstractIn 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.
KeywordCombinatorial optimization Locations of lines Line-capacitated Steiner trees Approximation algorithms Exact algorithms
DOI10.1007/s10898-022-01163-x
Indexed BySCI
Language英语
Funding ProjectNational 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 AreaOperations Research & Management Science ; Mathematics
WOS SubjectOperations Research & Management Science ; Mathematics, Applied
WOS IDWOS:000806126100002
PublisherSPRINGER
Citation statistics
Document Type期刊论文
Identifierhttp://ir.amss.ac.cn/handle/2S8OKBNM/61494
Collection中国科学院数学与系统科学研究院
Corresponding AuthorLi, Jianping
Affiliation1.Yunnan Univ, Dept Math, East Outer Ring South Rd, Kunming 650504, Yunnan, Peoples R China
2.Chinese Acad Sci, Acad Math & Syst Sci, Inst Appl Math, 55 Zhongguancun East Rd, Beijing 100190, Peoples R China
3.Beijing Univ Chem Technol, Sch Math & Phys, 15 North Third Ring East Rd, Beijing 100029, Peoples R China
Recommended Citation
GB/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
All comments (0)
No comment.
 

Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.