Report Number: CS-TR-88-1227
Institution: Stanford University, Department of Computer Science
Title: Finding Minimum-Cost Flows by Double-Scaling
Author: Ahuja, R. K.
Author: Goldberg, A. V.
Author: Orlin, J. B.
Author: Tarjan, R. E.
Date: October 1988
Abstract: Several researchers have recently developed new techniques
that give fast algorithms for the minimum-cost flow problem.
In this paper we combine several of these techniques to yield
an algorithm running in O(nm log log Ulog(nC)) time on
networks with n vertices, m edges, maximum arc capacity U,
and maximum arc cost magnitude C. The major techniques used
are the capacity-scaling approach of Edmonds and Karp, the
excess-scaling approach of Ahuja and Orlin, the cost-scaling
approach Goldberg and Tarjan, and the dynamic tree data
structure of Sleator and Tarjan. For nonsparse graphs with
large maximum arc capacity, we obtain a similar but slightly
better bound. We also obtain a slightly better bound for the
(noncapacitated) transportation problem. In addition, we
discuss a capacity-bounding approach to the minimum-cost flow