A scaling out-of-kilter algorithm for minimum cost flow

The out–of–kilter algorithm is one of the basic algorithms that solve the minimum cost flow problem. Its drawback is that it can improve the objective function at each iteration by only a small value. Consequently, it runs in pseudo–polynomial time. In this paper, the author describes a new out–of–kilter algorithm for minimum cost flow that runs in polynomial time. The new algorithm is a scaling algorithm and improves the objective function at each time by a ‘sufficiently large’ value.