KMS Of Academy of mathematics and systems sciences, CAS
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 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. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment