Accession Number : ADA254368


Title :   A Natural Randomization Strategy for Multicommodity Flow and Related Algorithms


Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Goldberg, Andrew V


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a254368.pdf


Report Date : Jul 1991


Pagination or Media Count : 14


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 :   *ALGORITHMS , *NETWORK FLOWS , STRATEGY , TIME , FLOW


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE