A Natural Randomization Strategy for Multicommodity Flow and Related Algorithms
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Operations Research