A linear time algorithm for the unbalanced Hitchcock transportation problem. Issue 2 (24th December 2015)

• Record Type: Journal Article
• Authors: Matsui, Tomomi; Scheifele, Rudolf
• Is Part Of: Networks. Volume 67:Issue 2(2016)
• Page Start: 170
• Page End: 182
• Publication Date: 2015-12-24
• Subjects: Hitchcock transportation problem -- minimum cost flow problem -- linear time algorithm -- recursive algorithm -- bipartite graph -- parallel edges; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21668
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract : 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. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 67(2), 170–182 2016