You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format. However, this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the Department of Computer Science of the University of Maryland at College Park under terms that include this permission. All other rights are reserved by the author(s).
Alok Aggarwal. Amotz Bar-Noy. Samir Khuller. Dina Kravets. Baruch Schieber. December 1993.
Efficient Minimum Cost Matching and Transportation Using. 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) University of Maryland Institute for Advanced Computer Studies, Dept. of Computer Science, Univ. of Maryland,
Last Generated Fri Aug 11 04:01:01 EDT 2000