A Cycle Augmentation Algorithm for Minimum Cost Multicommodity Flows on a Ring

Minimum cost multicommodity flows are a useful model for bandwidth allocation problems in telecommunications networks. These problems are arising more frequently as regional service providers wish to carry their traffic over some national core network. We describe a simple and practical combinatorial algorithm to find a minimum cost multicommodity flow in a ring network. Apart from 1 and 2-commodity flow problems, this seems to be the only such "combinatorial algorithm" for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each link by one, we may also find an integral routing of no greater cost. The "pivots" in the algorithm are determined by choosing an epsilon > 0, increasing and decreasing sets of variables, and adjusting these variables up or down accordingly by epsilon. In this sense, it generalizes the cycle cancelling algorithms for single source mincost flow. Although the algorithm is easily stated, proof of its correctness and polynomially bounded running time are more complex.