Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with monge costs

We consider a transportation problem where the cost matrix satisfies the Monge property. The problem has supply nodes N 1 (| N 1 | = n 1 ), demand nodes N 2 (| N 2 | = n 2 ), supply s i ≥ 0 for i ∈ N 1 , and demand d j ≥ 0 for j ∈ N 2 ( n = n 1 + n 2 , m = n 1 n 2 ). When the total supply is equal to the total demand, the problem can be solved in O ( n ) time using the northwest corner rule (Hoffman [10]). This algorithm and run‐time, however, do not extend to the unbalanced case, where the total supply is not equal to the total demand. The fastest strongly polynomial run‐time for the unbalanced transportation problem with Monge costs is O ( n log n ( m + n log n )), and for the unbalanced assignment problem (unit supplies and demands) with Monge costs is O ( n ( m + n log n )). In this article, we describe a simple algorithm that solves the unbalanced transportation problem with Monge costs in O ( mn 1 ) time and the unbalanced assignment problem with Monge costs in O ( m ) time using elementary data structures. We also develop a faster implementation of the algorithm that utilizes a heap, a self‐balancing binary search tree, and dynamic trees, and solves the transportation problem with Monge costs in O ( m log n 1 ) time. Our algorithms improve the run‐times for: (i) the unbalanced transportation problem with Monge costs by a factor of n log n /log n 1 or better and (ii) the unbalanced assignment problem with Monge costs by a factor of n or better. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013