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 -