ECCC-Report TR06-008https://eccc.weizmann.ac.il/report/2006/008Comments and Revisions published for TR06-008en-usThu, 19 Jan 2006 06:50:31 +0200
Paper TR06-008
| Polylogarithmic Approximation Algorithm for Non-Uniform Multicommodity Buy-at-Bulk |
MohammadTaghi Hajiaghayi,
Guy Kortsarz,
Mohammad R. Salavatipour
https://eccc.weizmann.ac.il/report/2006/008We 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.
Thu, 19 Jan 2006 06:50:31 +0200https://eccc.weizmann.ac.il/report/2006/008