Approximating Some Network Design Problems with Node Costs

We study several multi-criteria undirected network design problems with node costs and lengths with all problems related to the node costs

Multicommodity Buy at Bulk

(

mbb

) problem in which we are given a graph

G

 = (

V

,

E

), demands {

d

st

:

s

,

t

 ∈ 

V

}, and a family {

c

v

:

v

 ∈ 

V

} of subadditive cost functions. For every

s

,

t

 ∈ 

V

we seek to send

d

st

flow units from

s

to

t

on a single path, so that ∑ 

v

c

v

(

f

v

) is minimized, where

f

v

the total amount of flow through

v

. In the

Multicommodity Cost-Distance

(

mcd

) problem we are also given lengths {ℓ(

v

):

v

 ∈ 

V

}, and seek a subgraph

H

of

G

that minimizes

c

(

H

) + ∑ 

s

,

t

 ∈ 

V

d

st

·ℓ

H

(

s

,

t

), where ℓ

H

(

s

,

t

) is the minimum ℓ-length of an

st

-path in

H

. The approximation for these two problems is equivalent up to a factor arbitrarily close to 2. We give an

O

(log

3

n

)-approximation algorithm for both problems for the case of demands polynomial in

n

. The previously best known approximation ratio for these problems was

O

(log

4

n

) [Chekuri et al., FOCS 2006] and [Chekuri et al., SODA 2007]. This technique seems quite robust and was already used in order to improve the ratio of Buy-at-bulk with protection (Antonakopoulos et al FOCS 2007) from log

3

h

to log

2

h

. See ?.

We also consider the

Maximum Covering Tree

(

maxct

) problem which is closely related to

mbb

: given a graph

G

 = (

V

,

E

), costs {

c

(

v

):

v

 ∈ 

V

}, profits {

p

(

v

):

v

 ∈ 

V

}, and a bound

C

, find a subtree

T

of

G

with

c

(

T

) ≤ 

C

and

p

(

T

) maximum. The best known approximation algorithm for

maxct

[Moss and Rabani, STOC 2001] computes a tree

T

with

c

(

T

) ≤ 2

C

and

p

(

T

) = Ω(

opt

/log

n

). We provide the first nontrivial lower bound and in fact provide a

bicriteria

lower bound on approximating this problem (which is stronger than the usual lower bound) by showing that the problem admits no better than Ω(1/(loglog

n

)) approximation assuming

$\mbox{NP}\not\subseteq \mbox{Quasi(P)}$

even if the algorithm is allowed to violate the budget by any universal constant ρ

. This disproves a conjecture of [Moss and Rabani, STOC 2001].

Another related to

mbb

problem is the

Shallow Light Steiner Tree

(

slst

) problem, in which we are given a graph

G

 = (

V

,

E

), costs {

c

(

v

):

v

 ∈ 

V

}, lengths {ℓ(

v

):

v

 ∈ 

V

}, a set

U

 ⊆ 

V

of terminals, and a bound

L

. The goal is to find a subtree

T

of

G

containing

U

with

diam

ℓ

(

T

) ≤ 

L

and

c

(

T

) minimum. We give an algorithm that computes a tree

T

with

c

(

T

) = 

O

(log

2

n

) ·

opt

and

diam

ℓ

(

T

) = 

O

(log

n

) ·

L

. Previously, a polylogarithmic bicriteria approximation was known only for the case of edge costs and edge lengths.