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

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.