A geometrical explanation for the optimality concept of minimum cost flows

作者：Ghiyasvand M^*

来源：Scientia Iranica, 2016, 23(6): 3063-3071.

• The minimum cost-flow problem
• Out-of-kilter
• Most positive cut canceling

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).

• 出版日期2016