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 Gaxg & Konemann [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 multi-commodity flow problem.