Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design Problems

We consider approximation algorithms for non-uniform buy-at- bulk network design problems, in particular the multicommodity version. Hajiaghayi, Kortsarz and Salvatipour obtained a first poly-logarithmic approximation in recent work cite{HKS1,HKS2}. We build on their insights and provide an approach using two high level tools: probabilistic approximation of a graph metric by its spanning trees, and an LP relaxation for the single-source problem. This enables us to obtain a simpler description of the algorithms and proofs, and in some cases, improved approximation ratios. For the multicommodity problem on h pairs we obtain an approximation ratio of O(gamma(h^2) log^3 h) where gamma(n) is the worst case distortion in embedding the metric induced by a n node graph upper bound on gamma(n) yields an O(log^5 h) approximation ratio.