EQUIVALENCE OF THE PRIMAL AND DUAL SIMPLEX ALGORITHMS FOR THE MAXIMUMFLOW PROBLEM

Authors
AHUJA RK ORLIN JB
Citation
Rk. Ahuja et Jb. Orlin, EQUIVALENCE OF THE PRIMAL AND DUAL SIMPLEX ALGORITHMS FOR THE MAXIMUMFLOW PROBLEM, Operations research letters, 20(3), 1997, pp. 101-108
Citations number
7
Categorie Soggetti
Operatione Research & Management Science","Operatione Research & Management Science
Journal title
Operations research letters → ACNP
ISSN journal
01676377
Volume
20
Issue
3
Year of publication
1997
Pages
101 - 108
Database
ISI
SICI code
0167-6377(1997)20:3<101:EOTPAD>2.0.ZU;2-B
Abstract
In this paper, we study the primal and dual simplex algorithms for the maximum flow problem. We show that any primal simplex algorithm for t he maximum flow problem can be converted into a dual simplex algorithm that performs the same number of pivots and runs in the same time. Th e converse result is also true though in a somewhat weaker form. (C) 1 997 Elsevier Science B.V.