Efficient minimum cost matching and transportation using the quadrangle inequality

Abstract

We present efficient algorithms for finding a minimum cost perfect matching, and for serving the transportation problem in bipartite graphs, G = (Sinks ⋃ Sources, Sinks × Sources), where |Sinks| = n, |Sources| = m, n ≤ m, and the cost function obeys the quadrangle inequality. First, we assume that ah the sink points and ah the source points lie on a curve that is homeomorphic to either a line or a circle and the cost function is given by the Euclidean distance along the curve. We present a linear time algorithm for the matching problem that is simpler than the algorithm of Karp and Li (Discrete Math.13 (1975), 129-142). We generalize our method to solve the corresponding transportation problem in O((m + n)log(m + n)) time, improving on the best previously known algorithm of Karp and Li. Next, we present an O(n log m) time algorithm for minimum cost matching when the cost array is a bitonic Monge array. An example of this is when the sink points lie on one straight line and the source points lie on another straight line. Finally, we provide a weakly polynomial algorithm for the transportation problem in which the associated cost array is a bitonic Monge array. Our algorithm for this problem runs in O(m log(Σmj = 1sj)) time, where di is the demand at the ith sink, sj is the supply available at the jth source, and Σni = 1di ≤ Σmj = 1sj. © 1995 Academic Press, Inc.