Tech Report CS-91-43

Faster Approximation Algorithms for the Unit-Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts

Philip Klein, Serge Plotkin, Clifford Stein and Eva Tardos

June 1991

Abstract:

We describe new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. Our algorithms are much faster than previously known algorithms. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications. Leighton and Rao used uniform-capacity concurrent flow to find an approximately ``sparsest cut'' in a graph, and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical, as it required solving a large linear program. We show that their method might be practical by giving an $O(m^2 \log m)$ expected-time randomized algorithm for their concurrent flow problem on an $m$-edge graph. Raghavan and Thompson used uniform-capacity concurrent flow to approximately solve a channel width minimization problem in VLSI. We give an $O(k^{3/2} (m + n \log n))$ expected-time randomized algorithm and an $O(k\min\{n,k\} (m+n\log n)\log k)$ deterministic algorithm for this problem when the channel width is $\Omega(\log n)$, where $k$ denotes the number of wires to be routed in an $n$-node, $m$-edge network.

(complete text in pdf)