Note on Weintraub’s Minimum-Cost Circulation Algorithm
Francisco Barahona, Éva Tardos · SIAM Journal on Computing · 1989
In 1974 Weintraub [Management Sci., 21 (1974), pp. 87–97] 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 [J. Assoc. Comput. Mach., 19 (1972), pp. 248–264] 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.