Tech Report CS-91-58

Approximating Concurrent Flow with Uniform Demands and Capacities: An Implementation

Philip N. Klein and Sarah Kang

September 1991


We have implemented the concurrent flow approximation algorithm described in ``Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities,'' by Klein, Stein, and Tardos, which appeared in STOC 90. The implemented algorithm works for unit demands and unit capacities, and makes use of the idea of randomized path selection introduced in that paper. We make use of a simplification of the path selection technique proposed by A. Golderg. The implemented algorithm differs from the published algorithm in another respect as well: an effort is made to keep small the number of flow paths used to realize the concurrent flow. This paper describes our experience with the implementation thus far and our plans for further experimentation.

(complete text in pdf)