Accession Number:

ADA254340

Title:

Polynomial Dual Network Simplex Algorithms

Descriptive Note:

Corporate Author:

STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Orlin, James B.
• Plotkin, Serge A.
• Tardos, Eva

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.

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