TY - CONF
T1 - Efficient minimum cost matching using quadrangle inequality
T2 - Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on
Y1 - 1992
A1 - Aggarwal,A.
A1 - Bar-Noy,A.
A1 - Khuller, Samir
A1 - Kravets,D.
A1 - Schieber,B.
KW - algorithm;
KW - array;
KW - bipartite
KW - bitonic
KW - blue
KW - complexity;
KW - computational
KW - cost
KW - distance;
KW - Euclidean
KW - function;
KW - geometry;
KW - graph
KW - graphs;
KW - inequality;
KW - linear
KW - MATCHING
KW - matching;
KW - minimisation;
KW - minimum
KW - Monge
KW - perfect
KW - points;
KW - polynomial
KW - problem;
KW - quadrangle
KW - red
KW - theory;
KW - TIME
KW - transportation
KW - transportation;
KW - weakly
AB - The authors 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 les; m, and the cost function obeys the quadrangle inequality. The first results 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. They present a linear time algorithm for the matching problem. They generalize the method to solve the corresponding transportation problem in O((m+n)log(m+n)) time. The next result is an O(n log m) 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 (that is not necessarily parallel to the first one). Finally, they provide a weakly polynomial algorithm for the transportation problem in which the associated cost array is a bitonic Monge array
JA - Foundations of Computer Science, 1992. Proceedings., 33rd Annual Symposium on
M3 - 10.1109/SFCS.1992.267793
ER -