A scaling out-of-kilter algorithm for minimum cost flow
Laura Ciupală · 2005
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, we describe a new out-of-kilter algorithm for minimum cost flow that runs in polynomial time. Our algorithm is a scaling algorithm and improves the objective function at each time by a ”sufficiently large” value.