Hardness of buy-at-bulk network design
17 October 2004
We consider the Buy-at-Bulk network design problem in which we wish to design a network for carrying multicommodity demands from a set of source nodes to a set of destination nodes. The key feature of the problem is that the cost of capacity on each edge is concave and hence exhibits {em economies of scale}. If the cost of capacity per unit length can be different on different edges then we say that the problem is non-uniform. The problem is uniform otherwise. We show that for any constant $gamma$, if $NP$ is not contained in $ZPTIME(n^{polylog n})$ then there is no $O(log^{frac{1}{2}-gamma} N)$-approximation algorithm for non- uniform Buy-at-Bulk network design and there is no $O(log^{frac{1}{4}-gamma} N)$-approximation algorithm for the uniform problem.
