Shigeno et al.'s algorithm(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 to the optimality concept. For a network with $n$ nodes and $m$ arcs, the algorithm performs $O(log (nU))$ phases and runs in $O(m(m+nlog n)log (nU))$ time (where $U$ is the largest absolute arc bound ), which is $O(m(m+nlog n)log n)$ under the similarity assumption. This time is the running time of the algorithms by Orlincite{O} and Vygencite{V} which are the best strongly polynomial-time algorithms to solve this problem.
Ghiyasvand, M. (2016). A Geometrical Explanation to the Optimality Concept of Minimum Cost Flows. Scientia Iranica, 23(6), 3063-3071. doi: 10.24200/sci.2016.4012
MLA
Mehdi Ghiyasvand. "A Geometrical Explanation to the Optimality Concept of Minimum Cost Flows". Scientia Iranica, 23, 6, 2016, 3063-3071. doi: 10.24200/sci.2016.4012
HARVARD
Ghiyasvand, M. (2016). 'A Geometrical Explanation to the Optimality Concept of Minimum Cost Flows', Scientia Iranica, 23(6), pp. 3063-3071. doi: 10.24200/sci.2016.4012
VANCOUVER
Ghiyasvand, M. A Geometrical Explanation to the Optimality Concept of Minimum Cost Flows. Scientia Iranica, 2016; 23(6): 3063-3071. doi: 10.24200/sci.2016.4012
)