## Abstract

In this paper, we are concerned with maximum flow problems with non-zero lower bounds. The common approach to this problem is transforming the network into a bigger one with zero lower bounds, whose optimal solution yields a feasible solution to the original problem and then using one of the established methods for maximum flow problems with little to no modifications. Expanding upon the labelling techniques of Goldfarb and Hao we show that a variant of the monotonic build-up simplex algorithm runs in strongly polynomial time on the original network. The main characteristic of the MBU algorithm is that starting from an arbitrary basis solution it decreases the number of infeasible variables monotonically, without letting any feasible variables turn infeasible in the process. We show that this algorithm terminates after at most pivots which makes it the first strongly polynomial pivot algorithm that solves the problem without transforming the network.

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

Pages (from-to) | 39-47 |

Number of pages | 9 |

Journal | Optimization |

Volume | 63 |

Issue number | 1 |

Early online date | 6 Jun 2013 |

DOIs | |

Publication status | Published - 1 Jan 2014 |

## Keywords

- maximum flow problem
- MBU algorithm
- network flows
- pivot algorithm