We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of minimal dependency on the number of commodities k. We show that by modifying the algorithms by Garg & Konemann and Fleischer we can reduce their running time to a logarithmic dependence on k, and essentially match the running time of Fleischer’s FPTAS for the maximum multicommodity flow problem if we want only an implicit representation of the solution flow. In case we want to calculate explicitly the solution flow, our schemes run in time poly-logarithmic in nk (n is the number of nodes in the network). This is within a poly-logarithmic factor of the trivial lower bound of \Omega(nk).
Citation
Dept. of Computing & Software, McMaster University, Rm. ITB/218 1280 Main St. W. Hamilton, ON L8S 4K1 CANADA June 2003