Approximation algorithms for node-weighted buy-at-bulk network design
Chandra Chekuri, Mohammad Taghi Hajiaghayi, Guy Kortsarz, Mohammad R. Salavatipour · Symposium on Discrete Algorithms · 2007
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(log4h) approximation for the multi-commodity non-uniform buy-at-bulk network design problem.