Efficient Minimum Cost Matching and Transportation Using
Quadrangle Inequality

Efficient Minimum Cost Matching and Transportation Using
Quadrangle Inequality

##### Files

##### Publication or External Link

##### Date

1998-10-15

##### Authors

Aggarwal, Alok

Bar-Noy, Amotz

Khuller, Samir

Kravets, Dina

Schieber, Baruch

##### Advisor

##### Citation

##### DRUM DOI

##### 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)