Negative circuits for flows and submodular flows (Q1192951): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claims
RedirectionBot (talk | contribs)
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
    0 references
    0 references

    Identifiers