A geometrical explanation for the optimality concept of minimum cost flows

The algorithm proposed by Shigeno et al. (2000) is a scaling method to solve the minimum cost- ow problem. In each phase, they applied the most positive cut canceling idea. In this paper, we present a new approach to solve the problem, which uses the scaling method of Shigeno et al. (2000); but, in each phase, we apply the outof- kilter idea instead of the most positive cut canceling idea. Our algorithm is inspired by Ghiyasvand (2012). The algorithm gives a geometrical explanation for the optimality concept. For a network with n nodes and m arcs, the algorithm performs O(log(nU)) phases and runs in time O(m(m + n log n) log(nU)) (where U is the largest absolute arc bound), which is O(m(m+n log n) log n) under the similarity assumption. This time is the current best strongly polynomial time to solve the minimum cost- ow problem presented by Orlin (1993) and Vygen (2002).