A geometrical explanation for the optimality concept of minimum cost ows

The algorithm proposed by shigeno et al. (2000) is a scaling method to solve the minimum cost-flow 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 out of-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-flow problem presented by orlin (1993) and vygen (2002).