On strongly polynomial variants of the network simplex algorithm for the maximum flow problem

On strongly polynomial variants of the network simplex algorithm for the maximum flow problem

0.00 Avg rating—0 Votes
Article ID: iaor19921105
Country: Netherlands
Volume: 10
Issue: 7
Start Page Number: 383
End Page Number: 387
Publication Date: Oct 1991
Journal: Operations Research Letters
Authors: ,
Abstract:

The authors give a short proof that the network simplex algorithm with either the smaller label or the smallest label pivot rules proposed by D. Goldfarb and J. Hao, solves a maximum flow problem on an n-node, m-arc network in at most nm pivots and O(n2m) time. They also show that a straightforward adaptation of a shortest augmenting path algorithm is not polynomial.

Reviews

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