@inproceedings{e060b91198c742dca6d681edf4b7bafd,

title = "Approximation algorithms for node-weighted buy-at-bulk network design",

abstract = "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. • An O(log h) approximation for the single-sink nonuniform buy-at-bulk network design. Unless P = NP this ratio is tight up to constant factors. • An O(log4 h) approximation for the multi-commodity non-uniform buy-at-bulk network design problem.",

author = "C. Chekuri and Hajiaghayi, {M. T.} and G. Kortsarz and Salavatipour, {M. R.}",

note = "Funding Information: Supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta. Publisher Copyright: Copyright {\textcopyright} 2007 by the Association for Computing Machinery, Inc. and the Society for Industrial and Applied Mathematics.; 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 ; Conference date: 07-01-2007 Through 09-01-2007",

year = "2007",

language = "English (US)",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1265--1274",

booktitle = "Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007",

}