Polynomial dual network simplex algorithms

Polynomial dual network simplex algorithms

0.00 Avg rating0 Votes
Article ID: iaor19941946
Country: Netherlands
Volume: 60
Issue: 3
Start Page Number: 255
End Page Number: 276
Publication Date: Jul 1993
Journal: Mathematical Programming (Series A)
Authors: , ,
Abstract:

The authors show how to use polynomial and strongly polynomial capacity scaling algorithms for the transshipment problem to design a polynomial dual network simplex pivot rule. The present best pivoting strategy leads to an O(m2logn) 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, the authors also give an O(m(m+nlogn)min(lognB,mlogn))-time implementation of a strategy that requires somewhat more pivots.

Reviews

Required fields are marked *. Your email address will not be published.