TY - JOUR
T1 - Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems
AU - Illés, Tibor
AU - Richárd, Molnár-Szipai
PY - 2016/12/11
Y1 - 2016/12/11
N2 - The maximum flow problem (MFP) is a fundamental model in operations research. The network simplex algorithm is one of the most efficient solution methods for MFP in practice. The theoretical properties of established pivot algorithms for MFP are less understood. Variants of the primal simplex and dual simplex methods for MFP have been proven strongly polynomial, but no similar result exists for other pivot algorithms like the monotonic build-up or the criss-cross simplex algorithm.The monotonic build-up simplex algorithm (MBU SA) starts with a feasible solution, and fixes the dual feasibility one variable at a time, temporarily losing primal feasibility. In the case of maximum flow problems, pivots in one such iteration are all dual degenerate, bar the last one. Using a labelling technique to break these ties we show a variant that solves the maximum flow problem in 2|V||E|2 pivots.
AB - The maximum flow problem (MFP) is a fundamental model in operations research. The network simplex algorithm is one of the most efficient solution methods for MFP in practice. The theoretical properties of established pivot algorithms for MFP are less understood. Variants of the primal simplex and dual simplex methods for MFP have been proven strongly polynomial, but no similar result exists for other pivot algorithms like the monotonic build-up or the criss-cross simplex algorithm.The monotonic build-up simplex algorithm (MBU SA) starts with a feasible solution, and fixes the dual feasibility one variable at a time, temporarily losing primal feasibility. In the case of maximum flow problems, pivots in one such iteration are all dual degenerate, bar the last one. Using a labelling technique to break these ties we show a variant that solves the maximum flow problem in 2|V||E|2 pivots.
KW - maximum flow problem
KW - pivot algorithms
KW - MBU algorithm
KW - operations research
KW - polynomial
KW - simplex algorithms
KW - labelling technique
UR - http://www.sciencedirect.com/science/article/pii/S0166218X16303055
U2 - 10.1016/j.dam.2016.06.026
DO - 10.1016/j.dam.2016.06.026
M3 - Article
SN - 0166-218X
VL - 214
SP - 201
EP - 210
JO - Discrete Applied Mathematics
JF - Discrete Applied Mathematics
ER -