Accession Number:
ADA254368
Title:
A Natural Randomization Strategy for Multicommodity Flow and Related Algorithms
Descriptive Note:
Corporate Author:
STANFORD UNIV CA DEPT OF COMPUTER SCIENCE
Personal Author(s):
Report Date:
1991-07-01
Pagination or Media Count:
14.0
Abstract:
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.
Descriptors:
Subject Categories:
- Operations Research