Approximation algorithms for solving the line-capacitated minimum Steiner tree problem
文献类型：期刊论文
| 作者 | Li, Jianping1; Wang, Wencheng1; Lichen, Junran2,3; Liu, Suding1; Pan, Pengxiang1 |
| 刊名 | JOURNAL OF GLOBAL OPTIMIZATION
 |
| 出版日期 | 2022-06-06 |
| 页码 | 28 |
| 关键词 | Combinatorial optimization Locations of lines Line-capacitated Steiner trees Approximation algorithms Exact algorithms |
| ISSN号 | 0925-5001 |
| DOI | 10.1007/s10898-022-01163-x |
| 英文摘要 | 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. |
| 资助项目 | 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研究方向 | Operations Research & Management Science ; Mathematics |
| 语种 | 英语 |
| WOS记录号 | WOS:000806126100002 |
| 出版者 | SPRINGER |
| 源URL | [http://ir.amss.ac.cn/handle/2S8OKBNM/61493]  |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Li, Jianping |
| 作者单位 | 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 |
| 推荐引用方式 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. |
入库方式： OAI收割
来源：数学与系统科学研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。