Premium
New polynomial‐time cycle‐canceling algorithms for minimum‐cost flows
Author(s) -
Sokkalingam P. T.,
Ahuja Ravindra K.,
Orlin James B.
Publication year - 2000
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/1097-0037(200008)36:1<53::aid-net6>3.0.co;2-y
Subject(s) - binary logarithm , minimum cost flow problem , time complexity , mathematics , algorithm , polynomial , node (physics) , flow network , path (computing) , log log plot , flow (mathematics) , combinatorics , computer science , mathematical analysis , geometry , structural engineering , engineering , programming language
The cycle‐canceling algorithm is one of the earliest algorithms to solve the minimum‐cost flow problem. This algorithm maintains a feasible solution x in the network G and proceeds by augmenting flows along negative‐cost directed cycles in the residual network G ( x ) and thereby canceling them. For the minimum‐cost flow problem with integral data, the generic version of the cycle‐canceling algorithm runs in pseudopolynomial time, but several polynomial‐time specific implementations can be obtained by specifying the choices of cycles to be canceled. In this paper, we describe a new polynomial‐time implementation of the cycle‐canceling algorithm. Our algorithm is a scaling algorithm and proceeds by augmenting flows along negative cycles with “sufficiently large” residual capacity. Further, it identifies such a cycle by solving a shortest path problem with nonnegative arc lengths. For a network with n nodes and m arcs, our cycle‐canceling algorithm performs O ( m log( nU )) augmentations and runs in O ( m ( m + n log n ) log ( nU )) time, where U is an upper bound on the node supplies/demands and finite arc capacities. We also show that the cycle‐canceling algorithm (i) can solve the uncapacitated minimum‐cost flow problem in O ( n ( m + n log n ) log ( nU )) time; (ii) can obtain an integer optimal solution of the convex cost‐flow problem in O ( m ( m + n log n ) log ( nU )) time; and (iii) can be modified so that it runs in O ( m ( m + n log n ) min {log ( nU ), m log n }) time, which is a strongly polynomial time bound. © 2000 John Wiley & Sons, Inc.