A natural randomization strategy for multicommodity flow and related algorithms
Andrew V. Goldberg · Information Processing Letters · 1992
We consider the approximation algorithm of Leighton et. al. for the multicommodity flow problem. We give a more natural randomization strategy that is simpler than the one in the original algorithm and results in a better running time. This strategy also applies to several related algorithms.