The cost scaling algorithm for bipartite networks

Abstract

In this paper, we describe the cost scaling algorithm for the minimum cost flow in bipartite networks. The cost scaling algorithm for minimum cost flow problem in general networks, developed by Goldberg and Tarjan, is based on ε-optimality conditions. The basic idea behind the cost scaling algorithm for the minimum cost flow in a bipartite network is to perform bipushes from nodes in N₁. A bipush is a push over two consecutive admissible arcs. Consequently, a bipush moves the excess from a node in N₁ to another node in N₁. This approach has all the advantages of the scaling cost algorithm for the minimum cost flow in general networks. Moreover, it has an additional advantage that leads to an improved running time. This additional advantage consists in the fact that, using bipushes instead of pushes, all the nodes in N₂ are maintained balanced. Consequently, the running time of the cost scaling algorithm for the minimum cost flow is reduced from O(n²mlog(nB)) to O(n₁²mlog(nB)) when it is applied on bipartite networks.