A linear time algorithm for the unbalanced Hitchcock transportation problem

The Hitchcock transportation problem is a special case of the minimum cost flow problem where the graph is bipartite and capacities are infinite. If we let m denote the size of the larger and n the size of the smaller side of the bipartition, we call the Hitchcock transportation problem unbalanced if m is much larger than n. The unbalanced case arises in various applications, motivating the search for algorithms whose running time dependence on m is as small as possible. In this work, we give an algorithm with running time O ( m ( n ! ) 2 ) , which is the fastest known algorithm whose running time grows linearly in m. Moreover, we compare running times of algorithms for the Hitchcock transportation problem and the minimum cost flow problem and point out the fastest algorithms for particular relations of m and n, where m and n denote the number of edges and vertices in the context of the minimum cost flow problem.