A Geometrical Explanation to the Optimality Concept of Minimum Cost Flows

Abstract

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.