We present algorithms with poly-logarithmic approximation ratios for the buy-at-bulk network design problem in the node-weighted setting. We obtain the following results where  h  is the number of pairs in the input.   • On  O (log  h ) approximation for the single-sink non-uniform buy-at-bulk network design. Unless  P  =  NP  this ratio is tight up to constant factors.   • An  O (log 4   h ) approximation for the multi-commodity non-uniform buy-at-bulk network design problem.
['Chandra Chekuri', 'Mohammad Taghi Hajiaghayi', 'Guy Kortsarz', 'Mohammad R. Salavatipour']
Approximation algorithms for node-weighted buy-at-bulk network design