Approximation algorithms for solving the line-capacitated minimum Steiner tree problem

Jianping Li (), Wencheng Wang (), Junran Lichen (), Suding Liu () and Pengxiang Pan ()
Additional contact information
Jianping Li: Yunnan University
Wencheng Wang: Yunnan University
Junran Lichen: Chinese Academy of Sciences
Suding Liu: Yunnan University
Pengxiang Pan: Yunnan University

Journal of Global Optimization, 2022, vol. 84, issue 3, No 6, 687-714

Abstract: 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},\ldots , r_{n}\}$$ X = { r 1 , r 2 , … , r n } of n terminals in $${\mathbb {R}}^2$$ R 2 , a demand function $$d:X \rightarrow {\mathbb {N}}$$ 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$$ 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 $$T_l$$ T l ) 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 $$\sum _{e\in T_l}w(e)$$ ∑ e ∈ T l w ( e ) of such a Steiner tree $$T_l$$ T l among all line-capacitated Steiner trees mentioned-above, where weight $$w(e)=0$$ w ( e ) = 0 if two endpoints of that edge $$e\in T_l$$ e ∈ T l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge $$e\in T_l$$ e ∈ T l . In addition, when this line l is as an input in $${\mathbb {R}}^2$$ R 2 and $$\sum _{r\in X} d(r) \le C$$ ∑ r ∈ 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}$$ ρ st -approximation algorithm to solve the Euclidean minimum Steiner tree problem and a $$\rho _{1Lf}$$ ρ 1 L f -approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a $$(\rho _{st}\rho _{1Lf}+2)$$ ( ρ st ρ 1 L f + 2 ) -approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal $$r\in X$$ r ∈ X is less than $$\frac{C}{2}$$ C 2 , we provide a $$(\rho _{1Lf}+2)$$ ( ρ 1 L f + 2 ) -approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal $$r\in X$$ r ∈ X is at least $$\frac{C}{2}$$ 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.

Keywords: Combinatorial optimization; Locations of lines; Line-capacitated Steiner trees; Approximation algorithms; Exact algorithms (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10898-022-01163-x 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:jglopt:v:84:y:2022:i:3:d:10.1007_s10898-022-01163-x

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898

DOI: 10.1007/s10898-022-01163-x

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

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