POLYNOMIAL DUAL NETWORK SIMPLEX ALGORITHMS

被引：26

作者：

ORLIN, JB

PLOTKIN, SA

TARDOS, E

机构：

[1] MIT,SLOAN SCH MANAGEMENT SCI,CAMBRIDGE,MA 02139

[2] STANFORD UNIV,DEPT COMP SCI,STANFORD,CA 94305

[3] CORNELL UNIV,SCH OPERAT RES,ITHACA,NY 14853

来源：

MATHEMATICAL PROGRAMMING | 1993年 / 60卷 / 03期

关键词：

STRONGLY POLYNOMIAL; DUAL SIMPLEX ALGORITHM; NETWORK SIMPLEX ALGORITHM; MINIMUM COST NETWORK FLOWS;

D O I：

10.1007/BF01580615

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：255 / 276

页数：22