Premium
Canceling most helpful total cuts for minimum cost network flow
Author(s) -
Ervolina Thomas R.,
McCormick S. Thomas
Publication year - 1993
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230230106
Subject(s) - minimum cost flow problem , focus (optics) , dual (grammatical number) , dual polyhedron , mathematics , flow network , function (biology) , mathematical optimization , flow (mathematics) , conformal map , shortest path problem , maximum flow problem , path (computing) , duality (order theory) , computer science , linear programming , algorithm , combinatorics , graph , art , mathematical analysis , physics , geometry , literature , evolutionary biology , optics , biology , programming language
We present a polynomial algorithm for the minimum cost network flow problem (MCNF). It is a dual algorithm that is based on canceling positive augmenting cuts, which are the duals of negative augmenting cycles. We focus on canceling most helpful total cuts , which are cuts together with augmentation amounts that lead to the maximum possible increase in the dual objective function. We show how to compute a most helpful total cut and give a rigorous dual conformal decomposition theorem. Canceling most helpful cuts is, in spirit, dual to an algorithm of Weintraub as modified by Barahona and Tardos. We also show how our algorithm specializes to the case of shortest s–t path with nonnegative distances, show that this specialization is not finite for real data, and show that our bound on the number of cancellations is essentially tight. © 1993 by John Wiley & Sons, Inc.