|
Published Articles >> Table of Contents >> Abstract
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
pp. 677-686
Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design
C. Chekuri, University of Illinois, USA
M. T. Hajiaghayi, Carnegie Mellon University
G. Kortsarz, Rutgers University-Camden
M. R. Salavatipour, University of Alberta, Canada
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.15
Send link to a friend
| Abstract |
|
We consider approximation algorithms for non-uniform
buy-at-bulk network design problems. The first nontrivial
approximation algorithm for this problem is due to
Charikar and Karagiozova (STOC’ 05); for an instance on
h pairs their algorithm has an approximation guarantee of
exp\left( {O\left( {\sqrt {\log h\log \log h} } \right)} \right) for the uniform-demand case, and
logD · exp\left( {O\left( {\sqrt {\log h\log \log h} } \right)} \right) for the general demand
case, where D is the total demand. We improve upon this
result, by presenting the first poly-logarithmic approximation
for this problem. The ratio we obtain is O\left( {\log ^3 h \cdot \min \left\{ {\log D,\gamma \left( {h^2 } \right)} \right\}} \right) where h is the number of pairs and ?(n)
is the worst case distortion in embedding the metric induced
by a n vertex graph into a distribution over its spanning
trees. Using the best known upper bound on \gamma(n) we obtain
an O\left( {\min \left\{ {\log ^3 h \cdot \log D,\log ^5 h\log \log h} \right\}} \right) ratio approximation.
We also give poly-logarithmic approximations for some
variants of the singe-source problem that we need for the
multicommodity problem.
|
 Additional Information
|
Citation:
C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, M. R. Salavatipour,
"Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design,"
focs,
pp. 677-686,
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06),
2006
|
|
