Efficient Minimum Cost Matching and Transportation Using Quadrangle Inequality

Abstract

We present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G=(\Red\cup \Blue, \Red\times \Blue), where |\Red|=n, |\Blue|=m, n\le m, and the cost function obeys the quadrangle inequality. First, we assume that all the \red\ points and all the \blue\ 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 \cite{kl75}. 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 \cite{kl75}. 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 \red\ points lie on one straight line and the \blue\ 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(\sum_{j=1}^m \sj_j)) time, where \di_i is the demand at the ith sink, \sj_j is the supply available at the jth source, and \sum_{i=1}^n \di_i \le \sum_{j=1}^m \sj_j. (Also cross-referenced as UMIACS-TR-93-140)