|
Equivalence of primal simplex and dual simplex algorithms for the maximum flow problem R.K. Ahuja and J.B. Orlin, Operations Research Letters 20, 101-108, 1997 In this paper, we study the primal and dual simplex algorithms for the maximum flow problem. We show that any primal simplex algorithm for the maximum flow problem can be converted into a dual simplex algorithm that performs the same number of pivots and runs in the same time. T he converse result is also true though in a somewhat weaker form. |