A flurry of activity has recently occurred in algorithms for a variant of multicommodity flow called the maximum concurrent flow problem. Part of the interest is due to the fact that concurrent flow can be used in heuristics for finding separators in graphs, and these heuristics can be used in many other approximation algorithms.
An algorithm for concurrent flow also solves the multicommodity flow problem, an important problem in its own right in view of its applications in transportation planning, communication networks, and the like. Thus it is unfortunate that known exact algorithms for concurrent and multicommodity flow all have relatively high running times--hence the need for approximation algorithms. Sharokhi and Matula discovered the first approximation algorithm for concurrent flow. Their framework was further developed by Klein, Plotkin, Stein, and Tardos, who discovered a version that had a substantially better running time, and introduced a randomized technique that improved the running time even further. All these algorithms, however, have a significant drawback: they cannot handle edges with arbitrary capacities. This drawback is especially a hindrance in using concurrent flow to find small-weight separators in graphs, since in that context capacities are used to represent weights. This paper overcomes this drawback.
The paper makes use of (but extends) the techniques of those previous papers. Where the previous papers used shortest path calculation as a subroutine, this paper uses a more powerful subroutine for minimum-cost flow. Indeed, by adapting the randomized technique mentioned above, the authors show that a multicommodity flow problem with k commodities and m edges can be approximately solved by approximately solving O(k log2 m) minimum-cost flow problems.
This use of a more powerful subroutine is one of the two primary innovations reported in this paper; the other involves modifying a penalty function associated with overcongested edges to take capacities into account. In addition to these two main ideas, the paper describes two more technical methods for rounding demands and capacities in order to speed up the algorithm in certain cases. Recent experiments by Leong, Shor, and Stein indicate that the algorithm often outperforms the linear-programming–based codes, especially for instances with many commodities.
