We show that an ϵ-approximate solution of the cost-constrained K-commodity flow problem on an N-node M-arc network G can be computed by sequentially solving O(K(ϵ–2 + log K) log M log (ϵ–1K)) single-commodity minimum-cost flow problems on the same network. In particular, an approximate minimum-cost multicommodity flow can be computed in Õ(ϵ–2KNM) running time, where the notation Õ(·) means ‘up to logarithmic factors’. This result improves the time bound mentioned by Grigoriadis and Khachiyan by a factor of M/N and that developed more recently by Karger and Plotkin by a factor of ϵ–1. We also provide a simple Õ(NM)-time algorithm for single-commodity budget-constrained minimum-cost flows which is Õ(ϵ–3) times faster than the algorithm developed in the latter paper.
