A simple local-control approximation algorithm for multicommodity flow

In this paper, we describe a very simple (1+ε)-approximation algorithm for the multicommodity flow problem. The algorithm runs in time that is polynomial in N (the number of nodes in the network) and ε^-1 (the closeness of the approximation to optimal). The algorithm is remarkable in that it is much simpler than all known polynomial time flow algorithms (including algorithms for the special case of one-commodity flow). In particular, the algorithm does not rely on augmenting paths, shortest paths, min-cost paths, or similar techniques to push flow through a network. In fact, no explicit attempt is ever made to push flow towards a sink during the algorithm. Because the algorithm is so simple, it can be applied to a variety of problems for which centralized decision making and flow planning is not possible. For example, the algorithm can be easily implemented with local control in a distributed network and it can be made tolerant to link failures. In addition, the algorithm appears to perform well in practice. Initial experiments using the DIMACS generator of test problems indicate that the algorithm performs as well as or better than previously known algorithms, at least for certain test problems