TY - GEN

T1 - Approximation algorithms for non-uniform buy-at-bulk network design

AU - Chekuri, C.

AU - Hajiaghayi, M. T.

AU - Kortsarz, G.

AU - Salavatipour, M. R.

N1 - Copyright:
Copyright 2011 Elsevier B.V., All rights reserved.

PY - 2006

Y1 - 2006

N2 - 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(O(√log h log log h))for the uniform-demand case, and log · exp(O(√log h log log h)) 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 0(log3 h · min{log D, γ(h 2)}) 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 7(71) we obtain an O(min{log3 h· log D, log5 h log log h}) ratio approximation. We also give poly-logarithmic approximations for some variants of the singe-source problem that we need for the multicommodity problem.

AB - 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(O(√log h log log h))for the uniform-demand case, and log · exp(O(√log h log log h)) 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 0(log3 h · min{log D, γ(h 2)}) 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 7(71) we obtain an O(min{log3 h· log D, log5 h log log h}) ratio approximation. We also give poly-logarithmic approximations for some variants of the singe-source problem that we need for the multicommodity problem.

UR - http://www.scopus.com/inward/record.url?scp=34250370296&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34250370296&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2006.15

DO - 10.1109/FOCS.2006.15

M3 - Conference contribution

AN - SCOPUS:34250370296

SN - 0769527205

SN - 9780769527208

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 677

EP - 686

BT - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

T2 - 47th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2006

Y2 - 21 October 2006 through 24 October 2006

ER -