Approximating Buy-at-Bulk and Shallow-Light k-Steiner Trees

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

T

 ⊆ 

V

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\longrightarrow {\mathbb{R}}^+$

and a distance cost

$r:E\longrightarrow {\mathbb{R}}^+$

. The goal is to find a subtree

H

of

G

rooted at

s

with at least

k

terminals so that the cost ∑

$_{e\in{\it H}}$

b

(

e

)+∑

$_{t\in{\it T}-{\it s}}$

dist

(

t

,

s

) is minimize, 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 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

) over the edges, 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

$\frac{k}{8}$

terminals. Using this we obtain an (

O

(log

2

n

),

O

(log

4

n

))-approximation for the shallow-light

k

-Steiner tree and an

O

(log

4

n

)-approximation for the buy-at-bulk

k

-Steiner tree problem.