faster approximation schemes for fractional multicommodity flow problems
We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time independent of the number of commodities k. We show that by modifying the algorithms by Garg & Knemann [5] and Fleischer [3] we can reduce their running time to a logarithmic dependence on k, and essentially match the running time of [3] for the maximum multicommodity flow problem.
multicommodity flows