Negative circuits for flows and submodular flows (Q1192951): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Uwe T. Zimmermann / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Hiroshi Kise / rank | |||
Normal rank |
Revision as of 01:11, 22 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Negative circuits for flows and submodular flows |
scientific article |
Statements
Negative circuits for flows and submodular flows (English)
0 references
27 September 1992
0 references
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.
0 references
negative circuit method
0 references
minimum cost flow
0 references
submodular flow
0 references