Approximation algorithms for nonuniform buy-at-bulk network design

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

Research output: Contribution to journalArticle

Abstract

Buy-at-bulk network design problems arise in settings where the costs for purchasing or installing equipment exhibit economies of scale. The objective is to build a network of cheapest cost to support a given multicommodity flow demand between node pairs. We present approximation algorithms for buy-at-bulk network design problems with costs on both edges and nodes of an undirected graph. Our main result is the first poly-logarithmic approximation ratio for the non-uniform problem that allows different cost functions on each edge and node; the ratio we achieve is O(log4 h), where h is the number of demand pairs. In addition we present an O(log h) approximation for the single sink problem. Poly-logarithmic ratios for some related problems are also obtained. Our algorithm for the multicommodity problem is obtained via a reduction to the single source problem using the notion of junction trees. We believe that this presents a simple yet useful general technique for network design problems.

Original languageEnglish (US)
Pages (from-to)1772-1798
Number of pages27
JournalSIAM Journal on Computing
Volume39
Issue number5
DOIs
StatePublished - Feb 25 2010

Keywords

  • Approximation algorithm
  • Concave cost
  • Economies of scale
  • Network design
  • Network flow
  • Nonuniform buy-at-bulk

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

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

  • Cite this