On Minimum Concave Cost Multicommodity Flow

Moses Charikar
Department of Computer Science
Princeton University


Wednesday, August 17, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 453


Abstract:

We study a general network design problem where the goal is to find a minimum cost solution buying capacity on edges of a network so as to route demands between a given set of source-sink pairs. The cost of an edge in the graph is a concave monotone function of the flow crossing the edge and hence exhibits economy of scale - it pays to aggregate flow paths as much as possible. In the general (non-uniform) case, each edge has its own cost function, possibly different from other edges. Since such problems are computationally hard, we focus on approximation algorithms, i.e. efficient heuristics with provable guarantees.

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 number of vertices in the graph.

This is joint work with Adriana Karagiozova.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html