Picture water droplets

Developing mathematical theories of the physical world: Open Access research on fluid dynamics from Strathclyde

Strathprints makes available Open Access scholarly outputs by Strathclyde's Department of Mathematics & Statistics, where continuum mechanics and industrial mathematics is a specialism. Such research seeks to understand fluid dynamics, among many other related areas such as liquid crystals and droplet evaporation.

The Department of Mathematics & Statistics also demonstrates expertise in population modelling & epidemiology, stochastic analysis, applied analysis and scientific computing. Access world leading mathematical and statistical Open Access research!

Explore all Strathclyde Open Access research...

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

[img]
Preview
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

Abstract

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.