@inproceedings{c5ab4b20b7534ef28c89e4db47e6a6c9,
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 = "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",
address = "United States",
}