Note on Weintraub’s minimum-cost circulation algorithm

In 1974 Weintraub published an algorithm for the minimum-cost circulation problems with convex cost function. In this note Weintraub’s algorithm is considered when applied to a minimum-cost circulation problem with linear objective function. It is shown that a minor variation of the algorithm runs in polynomial time. The resulting algorithm, although it is not strongly polynomial, does not rely on scaling. It is a generalization of the maximum flow algorithm due to Edmonds and Karp that augments along the fattest augmenting path in the residual graph. The algorithm described here is slower than the fastest minimum-cost circulation algorithms known. The authors’ interest in the algorithm is partially historical, a scaling free ‘almost polynomial time’ algorithm was published in 1974, and partially due to the different ideas involved.