Accession Number : ADA254340


Title :   Polynomial Dual Network Simplex Algorithms


Corporate Author : STANFORD UNIV CA DEPT OF COMPUTER SCIENCE


Personal Author(s) : Orlin, James B ; Plotkin, Serge A ; Tardos, Eva


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a254340.pdf


Report Date : Aug 1991


Pagination or Media Count : 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 0(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 0(m(m + n log n) min(log nB, m log n))-time implementation of a strategy that requires somewhat more pivots.


Descriptors :   *ALGORITHMS , *NETWORK FLOWS , *PIVOTS , *SIMPLEX METHOD , INPUT , COMPUTATIONS , STRATEGY , NETWORKS , INTEGRALS , THEORY , NODES , TIME , POLYNOMIALS , MATHEMATICS , NUMBERS


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE