A Faster Minimum Cost Flow Algorithm: A New Scaling Approach to the Minimum Cost Flow Problem

We present several new algorithms for the minimum cost flow problem. These algorithms incorporate a number of approaches including (1) cost scaling, (2) capacity scaling, and (3) dynamic trees, as well as ideas from "strongly polynomial algorithm." The resulting time bound is the best known for solving the minimum cost flow problem.