Approximation algorithms for node-weighted buy-at-bulk network design

C. Chekuri, M. T. Hajiaghayi, G. Kortsarz, M. R. Salavatipour

Research output: Chapter in Book/Report/Conference proceedingConference contribution

21 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
PublisherAssociation for Computing Machinery
Pages1265-1274
Number of pages10
ISBN (Electronic)9780898716245
StatePublished - 2007
Event18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 - New Orleans, United States
Duration: Jan 7 2007Jan 9 2007

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
Volume07-09-January-2007

Other

Other18th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007
Country/TerritoryUnited States
CityNew Orleans
Period1/7/071/9/07

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Approximation algorithms for node-weighted buy-at-bulk network design'. Together they form a unique fingerprint.

Cite this