Picture map of Europe with pins indicating European capital cities

Open Access research with a European policy impact...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by Strathclyde researchers, including by researchers from the European Policies Research Centre (EPRC).

EPRC is a leading institute in Europe for comparative research on public policy, with a particular focus on regional development policies. Spanning 30 European countries, EPRC research programmes have a strong emphasis on applied research and knowledge exchange, including the provision of policy advice to EU institutions and national and sub-national government authorities throughout Europe.

Explore research outputs by the European Policies Research Centre...

Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems

Illés, Tibor and Richárd, Molnár-Szipai (2016) Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems. Discrete Applied Mathematics, 214. pp. 201-210. ISSN 0166-218X

Text (Illes-etal-DAM-2016-Strongly-polynomial-primal-monotonic-build-up-simplex-algorithm-for-maximal-flow-problems)
Illes_etal_DAM_2016_Strongly_polynomial_primal_monotonic_build_up_simplex_algorithm_for_maximal_flow_problems.pdf - Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo

Download (316kB) | Preview


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.