Negative circuits for flows and submodular flows (Q1192951)

The negative circuit method is one of the oldest and most straightforward ones for solving minimum cost flow problems. It was not known to be finite until Goldberg and Tarjan proposed the use of minimum mean circuits and proved polynomial bounds for the resulting method without using any scaling of the initial data, on which all previously known polynomial methods for solving minimum cost flow problems have relied. Minimum cost submodular flow problems firstly introduced by Edmonds and Giles are generalizations of the minimum cost flow problems and other related problems. Cui and Fujishige have developed a finite minimum mean circuit method for these problems. This background in view the paper introduces certain additional positive weights on negative circuits and proposes selecting a negative circuit with minimum ratio of cost and weight. The resulting negative circuit method with minimum ratio circuits has been proven to terminate after at most \(m\cdot U\) iterations, where \(m\) denotes the number of arcs and \(U\) the maximum capacity of arc.