Hardness of buy-at-bulk network design

摘要

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 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 /spl gamma/, if NP /spl nsube/ ZPTIME(n/sup polylog n/), then there is no O(log/sup 1/2 - /spl gamma//N)-approximation algorithm for non-uniform buy-at-bulk network design and there is no O(log/sup 1/4 - /spl gamma//N)-approximation algorithm for the uniform problem.