TR06-008 Authors: MohammadTaghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour

Publication: 19th January 2006 06:50

Downloads: 1149

Keywords:

We consider the non-uniform multicommodity buy-at-bulk network

design problem. In this problem we are given a graph $G(V,E)$ with

two cost functions on the edges, a buy cost $b:E\longrightarrow \RR^+$ and a rent cost

$r:E\longrightarrow\RR^+$, and a set of source-sink pairs $s_i,t_i\in V$ ($1\leq i\leq \alpha$)

with each pair $i$ having a positive demand $\delta_i$. Our goal is to design

a minimum cost network $G(V,E')$ such that for every $1\leq i\leq

\alpha$, $s_i$ and $t_i$ are in the

same connected component in $G(V,E')$. The

total cost of $G(V,E')$ is the sum of buy costs of the edges in $E'$

plus sum of total demand going through every edge in $E'$ times the

rent cost of that edge. Since the costs of different edges can be

different, we say that the problem is non-uniform. The first

non-trivial approximation algorithm for this problem is due to

Charikar and Karagiozova (STOC' 05) whose algorithm has an

approximation guarantee of $\exp(O(\sqrt{\log n\log\log n}))$,

when all $\delta_i=1$ and $\exp(O(\sqrt{\log N\log\log N}))$ for the general

demand case where $N$ is the sum of all demands. We improve upon this result, by

presenting the first polylogarithmic (specifically, $O(\log^4 n)$ for unit demands

and $O(\log^4 N)$ for the general demands)

approximation for this problem. The algorithm relies on a recent result

\cite{HKS1} for the buy-at-bulk $k$-Steiner tree problem.