Faster approximation schemes for fractional multicommodity flow problems

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k . We show that by modifying the algorithms by Garg and Könemann [1998] and Fleischer [2000], we can reduce their running time on a graph with n vertices and m edges from Õ (ε −2 ( m 2 + km )) to Õ (ε −2 m 2 ) for an implicit representation of the output, or Õ (ε −2 ( m …