On strongly polynomial variants of the networks simplex algorithm for the maximum flow problem (Q1180817)

The specialization of the primal simplex method known as the network simplex algorithm can be used to solve a network flow problem. Recently, the authors [Math. Program., Ser. A 47, No. 3, 353-365 (1990; Zbl 0713.90028)] proved that this algorithm with what they called the smallest label and smaller label pivot rules solves a maximum flow problem on an \(n\)-node, \(m\)-arc network in at most \(nm\) and \(2nm\) pivots, respectively, and \(O(n^ 2 m)\) time. Here, the authors provide a much shorter and simpler proof of these results. This proof uses a new and interesting potential function to obtain a bound of \(nm\) on the number of pivots for both rules. The authors also show that a straightforward simplex adaptation of the Edmonds-Karp-Dinic shortest augmenting path algorithm is not polynomial.