Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR06-008 | 23rd November 2005 00:00

Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk



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.

ISSN 1433-8092 | Imprint