POLYNOMIAL DUAL NETWORK SIMPLEX ALGORITHMS

Authors
ORLIN JB PLOTKIN SA TARDOS E
Citation
Jb. Orlin et al., POLYNOMIAL DUAL NETWORK SIMPLEX ALGORITHMS, Mathematical programming, 60(3), 1993, pp. 255-276
Citations number
13
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Applications & Cybernetics
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
60
Issue
3
Year of publication
1993
Pages
255 - 276
Database
ISI
SICI code
0025-5610(1993)60:3<255:PDNSA>2.0.ZU;2-O
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(m 2 log n) bound on the number of pivots, where n and m denotes the numb er 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.