BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-91-1374
       ENTRY:: September 02, 1994
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Polynomial dual network simplex algorithms
        TYPE:: Technical Report
      AUTHOR:: Orlin, James B.
      AUTHOR:: Plotkin, Serge A.
      AUTHOR:: Tardos, Eva
        DATE:: August 1991
       PAGES:: 25
    ABSTRACT:: We show how to use polynomial and strongly polynomial
               capacity scaling algorithms for the transshipment problem to
               design a polynomial dual network simplex pivot rule. Our best
               pivoting strategy leads to an O(m2 log n) bound on the number
               of pivots, where n and m denotes the number of nodes and arcs
               in the input network. If the demands are integral and at most
               B, we also give an O(m(m + n log n) min(log nB, m log
               n))-time implementation of a strategy that requires somewhat
               more pivots.
       NOTES:: [Adminitrivia V1/RAM/19940902]
         END:: STAN//CS-TR-91-1374