Research Output per year

### 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 is 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 (MBUSA) starts with a feasible solution, and fixes the dual feasibility one variable 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||A|2 pivots.

Original language | English |
---|---|

Number of pages | 16 |

Volume | 2015 |

Publication status | Published - 1 Sep 2015 |

### Publication series

Name | Operations Research Report |
---|---|

Publisher | ELTE |

ISSN (Print) | 1215-5918 |

### Keywords

- maximum flow problem
- pivot algorithm
- monotonic build-up simplex algorithm

## Fingerprint Dive into the research topics of 'Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems'. Together they form a unique fingerprint.

## Research Output

- 1 Article

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

Illés, T. & Richárd, M-S., 11 Dec 2016, In : Discrete Applied Mathematics. 214, p. 201-210 10 p.Research output: Contribution to journal › Article

Open Access

File

## Cite this

Illes, T., & Molnár-Szipai, R. (2015).

*Strongly polynomial primal monotonic build-up simplex algorithm for maximal flow problems*. (Operations Research Report).