Finding Minimum-Cost Flows by Double Scaling
Ravindra K. Ahuja, Andrew V. Goldberg, James B. Orlin, Robert Endre Tarjan · 1988
Several researchers have recendy develof)ed new techniques that give fast aJgorithms for the minimuin-cost flow problem.In this paper we combine several of these techniques to yield an algorithm running in 0{nm log log U log(nC)) time on networks with n vertices, m arcs, ma.ximum arc capacity U, and maximum arc cost magnitude C. TTie major techniques usedare the capacity-scaling approach of Edmonds and Karp, the excess-scaling approach of Ahuja and Orlin, the cost-scaling approach of 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 (uncapaciiated) transportation problem.In addition, we discuss a capacity-bounding approach to the minimum-cost flow problem.