TY - JOUR

T1 - Approximating buy-at-bulk and shallow-light k-steiner trees

AU - Hajiaghayi, Mohammad Taghi

AU - Kortsarz, Guy

AU - Salavatipour, Mohammad R.

N1 - Funding Information:
M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta.
Funding Information:
M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02.

PY - 2009/1

Y1 - 2009/1

N2 - We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals TV including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ ℝ + and a distance cost r:E→ ℝ +. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ e H b(e)+ ∑ t T-s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log∈ 4 n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log∈n),O(log∈ 3 n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log∈ 2 n),O(log∈ 4 n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log∈ 4 n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 677-686, 2006).

AB - We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals TV including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ ℝ + and a distance cost r:E→ ℝ +. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ e H b(e)+ ∑ t T-s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log∈ 4 n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log∈n),O(log∈ 3 n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log∈ 2 n),O(log∈ 4 n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log∈ 4 n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 677-686, 2006).

UR - http://www.scopus.com/inward/record.url?scp=58149489621&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58149489621&partnerID=8YFLogxK

U2 - 10.1007/s00453-007-9013-x

DO - 10.1007/s00453-007-9013-x

M3 - Article

AN - SCOPUS:58149489621

SN - 0178-4617

VL - 53

SP - 89

EP - 103

JO - Algorithmica (New York)

JF - Algorithmica (New York)

IS - 1

ER -