Finding Minimum-Cost Circulations by Canceling Negative Cycles
Report ID: TR-107-87Author: Tarjan, Robert E. / Goldberg, Andrew V.
Date: 1987-07-00
Pages: 18
Download Formats: |PDF|
Abstract:
A classical algorithm for finding a minimum-cost circulation consists of repeatedly finding a residual cycle of negative cost and canceling it by pushing enough flow around the cycle to saturate an arc. We show that a judicious choice of cycles for canceling leads to a polynomial bound on the number of iterations in this algorithm. This gives a very simple strongly polynomial algorithm that uses no scaling. A variant of the algorithm that uses dynamic trees runs in O(nm(log n) min{log(nC), mlog n}) time on a network of n vertices, m arcs, and arc costs of maximum absolute value C. This bound is comparable to those of the fastest previously known algorithms.