Faster Approximate Multicommodity Flow Using Quadratically Coupled Flows

Jonathan A. Kelner, Gary Miller, Richard Peng

The maximum multicommodity flow problem is a natural generalization of the maximum flow problem to route multiple distinct flows. Obtaining a $1-\epsilon$ approximation to the multicommod…