Accession Number:

ADA254340

Title:

Polynomial Dual Network Simplex Algorithms

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Report Date:

1991-08-01

Pagination or Media Count:

25.0

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 0m2 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 0mm n log n minlog nB, m log n-time implementation of a strategy that requires somewhat more pivots.

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE