APPROXIMATION ALGORITHMS FOR NONUNIFORM BUY-AT-BULK NETWORK DESIGN

作者：Chekuri C^*; Hajiaghayi M T; Kortsarz G; Salavatipour M R

来源：SIAM Journal on Computing, 2010, 39(5): 1772-1798.

DOI：10.1137/090750317

• nonuniform buy-at-bulk
• network design
• approximation algorithm
• concave cost
• network flow
• economies of scale

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(log(4) 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.

• 出版日期2010