TY - GEN
T1 - Approximation Algorithms for Priority Steiner Tree Problems
AU - Sahneh, Faryad Darabi
AU - Kobourov, Stephen
AU - Spence, Richard
N1 - Funding Information:
The authors wish to thank Alon Efrat and Spencer Krieger for their discussions related to the priority NWST problem.
Funding Information:
Supported in part by NSF grants CCF-1740858, CCF-1712119, and DMS-1839274.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - In the Priority Steiner Tree (PST) problem, we are given an undirected graph G= (V, E) with a source s∈ V and terminals T⊆ V\ { s}, where each terminal v∈ T requires a nonnegative priority P(v). The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from s to each terminal v consists of edges of rate greater than or equal to P(v). The PST problem with k priorities admits a min { 2 ln | T| + 2, kρ} -approximation [Charikar et al., 2004], and is hard to approximate with ratio clog log n for some constant c [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the (2 ln | T| + 2 ) -approximation to show an approximation ratio of ⌈ log 2| T| ⌉ + 1 ≤ 1.443 ln | T| + 2, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a (2 ln | T| + 2 ) -approximation using extensions of the spider decomposition by [Klein & Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight.
AB - In the Priority Steiner Tree (PST) problem, we are given an undirected graph G= (V, E) with a source s∈ V and terminals T⊆ V\ { s}, where each terminal v∈ T requires a nonnegative priority P(v). The goal is to compute a minimum weight Steiner tree containing edges of varying rates such that the path from s to each terminal v consists of edges of rate greater than or equal to P(v). The PST problem with k priorities admits a min { 2 ln | T| + 2, kρ} -approximation [Charikar et al., 2004], and is hard to approximate with ratio clog log n for some constant c [Chuzhoy et al., 2008]. In this paper, we first strengthen the analysis provided by [Charikar et al., 2004] for the (2 ln | T| + 2 ) -approximation to show an approximation ratio of ⌈ log 2| T| ⌉ + 1 ≤ 1.443 ln | T| + 2, then provide a very simple, parallelizable algorithm which achieves the same approximation ratio. We then consider a more difficult node-weighted version of the PST problem, and provide a (2 ln | T| + 2 ) -approximation using extensions of the spider decomposition by [Klein & Ravi, 1995]. This is the first result for the PST problem in node-weighted graphs. Moreover, the approximation ratios for all above algorithms are tight.
KW - Approximation algorithms
KW - Network design
KW - Priority steiner tree
UR - http://www.scopus.com/inward/record.url?scp=85118114578&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85118114578&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-89543-3_10
DO - 10.1007/978-3-030-89543-3_10
M3 - Conference contribution
AN - SCOPUS:85118114578
SN - 9783030895426
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 112
EP - 123
BT - Computing and Combinatorics - 27th International Conference, COCOON 2021, Proceedings
A2 - Chen, Chi-Yeh
A2 - Hon, Wing-Kai
A2 - Hung, Ling-Ju
A2 - Lee, Chia-Wei
PB - Springer Science and Business Media Deutschland GmbH
T2 - 27th International Conference on Computing and Combinatorics, COCOON 2021
Y2 - 24 October 2021 through 26 October 2021
ER -