On Non-uniform Multicommodity Buy-at-Bulk Network Design

COMPUTER SCIENCE/DISCRETE MATH, I
Topic:On Non-uniform Multicommodity Buy-at-Bulk Network Design
Speaker:Adriana Karagiozova
Affiliation:Princeton University
Date:Monday, April 25
Time/Room:11:15am - 12:15pm/S-101

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