×

Equivalence of the primal and dual simplex algorithms for the maximum flow problem. (English) Zbl 0882.90035

Summary: 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. The converse result is also true though in a somewhat weaker form.

MSC:

90B10 Deterministic network models in operations research
90C35 Programming involving graphs or networks
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows: theory, algorithms, and applications, (1993), Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] Armstrong, R.D.; Chen, W.; Goldfarb, D.; Jin, Z., Strongly polynomial dual simplex methods for the maximum flow problem, () · Zbl 0894.90058
[3] Armstrong, R.D.; Jin, Z., A strongly polynomial dual (simplex) method for the MAX flow problem, ()
[4] Goldberg, A.V.; Grigoriadis, M.D.; Tarjan, R.E., Use of dynamic trees in a network simplex algorithm for the maximum flow problem, Math. programming, 50, 277-290, (1991) · Zbl 0743.90107
[5] Goldfarb, D.; Chen, W., An O(n3) dual simplex method for the maximum flow problem, ()
[6] Goldfarb, D.; Hao, J., A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and O(n2m) time, Math. programming, 47, 353-365, (1990) · Zbl 0713.90028
[7] Goldfarb, D.; Hao, J., On strongly polynomial variants of the network simplex algorithm for the maximum flow problem, Oper. res. lett., 10, 383-387, (1990) · Zbl 0754.90025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.