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-c...
详细信息
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 are 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 are 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. (C) 2000 John Wiley & Sons, Inc.
暂无评论