Strongly polynomial complexity of some pivot algorithms on network flow problems

Event Date: 26 February 2016

Speaker: Tibor Illes, Management Science Department

Time: 1.30pm

Location: Strathclyde Business School, Cathedral Wing, CW506a

Abstract: In this joint work with Richárd Molnár-Szipai, we start with the summary of the most important types of network flow problems, and then discuss in more details the maximum flow problem.

One possible solution strategy to solve maximum flow problems is based on linear programming approach, already discussed by Dantzig in some of his early works in 1950’s. However, first result on efficiency, i.e. strongly polynomial complexity of a variant of primal simplex method is due to Goldfarb and Hao (Mathematical Programming, 1990).

To our best knowledge no other polynomial complexity result for any pivot algorithm that could solve maximum flow problem as special linear programming problem was known. We recently proved that a variant of the monotonic build-up simplex algorithm (MBU SA), developed by Anstreicher and Terlaky (Operations Research, 1994) is strongly polynomial on maximum flow problems. Interestingly enough that the MBU SA is neither a purely primal, nor a purely dual algorithm, thus during the iterations visits primal feasible and dual infeasible; neither primal nor dual feasible bases (spanning trees) until reaches the optimal basis.

At the end of our talk further research directions will be discussed.

Published: 23 February 2016