New methods for multi-commodity flows

AbstractMulti-commodity flow problems arise naturally in telecommunications and scheduling. Such applications typically involve large network optimization problems with constraints of a form which make standard optimization techniques inapplicable. Linear programming methods ccan solve only small instances of such problems. New theoretical work by Soviet researchers on network-based techniques is shown in this paper to yield practical algorithms which enable certain types of multi-commodity flow problems to be solved quickly. As these methods generalize efficient single-commodity methods, there is promise that further research will allow more general problems to be solved in an analogous manner