Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ϵ^–2+log k) log n) 1-commodity minimum-cost flow computations, where k is the number of commodities, n is the number of nodes, and ϵ is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem.