A cycle augmentation algorithm for minimum cost multicommodity flows on a ring

Minimum cost multicommodity flows are a useful model for bandwidth allocati on problems. These problems ale 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 c ost multicommodity flow in a ring network. Apart from 1 and 2-commodity flo w problems, this seems to be the only such "combinatorial augmentation algo rithm" for a version of exact mincost multicommodity flow. The solution it produces is always half-integral, and by increasing the capacity of each li nk by one, we may also find an integral routing of no greater cost. The "pi vots" in the algorithm are determined by choosing an epsilon > 0, increasin g and decreasing sets of variables, and adjusting these variables up or dow n accordingly by E, Ln this sense, it generalizes the cycle cancelling algo rithms for (single source) mincost flow. Although the algorithm is easily s tated, proof of its correctness and polynomially bounded running time are m ore complex. (C) 2001 Elsevier Science B.V. All lights reserved.