Computer Science/Discrete Mathematics Seminar I

We study the multicommodity buy-at-bulk network design problem where the goal is to buy capacity on edges of a network so as to enable the demands between a given set of source-sink pairs to be routed - the objective is to minimize the cost of such a solution. The key aspect of this problem is that the cost of an edge in the graph is a concave monotone function of the flow cross the edge and hence exhibits economy of scale - it pays to aggregate flow paths as much as possible. 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. We present the first non-trivial approximation algorithm for the general case. Our algorithm is an extremely simple randomized greedy algorithm, involving not much more than shortest path computations. We achieve an approximation guarantee of exp(O(sqrt(log(n)log(log(n)))) where n is the total demand in the graph. This is joint work with Moses Charikar