A bad network problem for the simplex method and other minimum cost flow algorithms

Abstract

For any integer n, a modified transportation problem with 2 n + 2 nodes is constructed which requires 2n + 2n-2-2 iterations using all but one of the most commonly used minimum cost flow algorithms. As a result, the Edmonds-Karp Scaling Method [3] becomes the only known "good" (in the sense of Edmonds) algorithm for computing minimum cost flows. © 1973 The Mathematical Programming Society.