BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-88-1227
       ENTRY:: April 24, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Finding Minimum-Cost Flows by Double-Scaling
        TYPE:: Technical Report
      AUTHOR:: Ahuja, R. K.
      AUTHOR:: Goldberg, A. V.
      AUTHOR:: Orlin, J. B.
      AUTHOR:: Tarjan, R. E.
        DATE:: October 1988
       PAGES:: 32
    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
               problem.
       NOTES:: [Adminitrivia V1/Prg/19950424]
         END:: STAN//CS-TR-88-1227