@article { author = {Ghiyasvand, Mehdi}, title = {A Geometrical Explanation to the Optimality Concept of Minimum Cost Flows}, journal = {Scientia Iranica}, volume = {23}, number = {6}, pages = {3063-3071}, year = {2016}, publisher = {Sharif University of Technology}, issn = {1026-3098}, eissn = {2345-3605}, doi = {10.24200/sci.2016.4012}, 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.}, keywords = {Operations research,Network Flows Optimization,The Minimum Cost Flow Proble}, url = {https://scientiairanica.sharif.edu/article_4012.html}, eprint = {https://scientiairanica.sharif.edu/article_4012_4b9e7302524d0960c3ecc694ae299f55.pdf} }