on non-uniform multicommodity buy-at-bulk network design
We study the multicommodity buy-at-bulk network design problem in which we seek to design a network that satisfies the demands between terminals from a given set of source-sink pairs. The key characteristic of this problem is the fact that the cost functions associated with the edges of the graph are sub-additive monotone and hence experience economies of scale . In the non-uniform case, each edge has its own cost function -- possibly different from other edges. Special cases of this problem have been studied extensively: there are approximation algorithms when the edge cost functions are identical or when all source-sink pairs share the same source. We present the first non-trivial approximation algorithm for the general case. Our algorithm is an extremely simple randomized greedy algorithm and has an approximation guarantee of exp( O ?ln n ln ln n )) when the instance has at most n source-sink pairs with unit demands. In the case of general demands, this yields an approximation factor of exp( O ?ln N ln ln N )), where N is the sum of all demands.
non-uniform multicommodity buy-at-bulk network network design design terminals cost functional association graph experience case approximation algorithms approximation algorithm sharing general randomization greedy algorithm factor