Efficient minimum cost matching using quadrangle inequality

Alok Aggarwal, Amotz Bar-Noy, Samir Khuller, Dina Kravets, Baruch Schieber

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations

Abstract

The authors present efficient algorithms for finding a minimum cost perfect matching, and for solving the transportation problem in bipartite graphs, G = (Red union Blue, Red ∗ Blue), where mod Red mod = n, mod Blue mod = m, n <or= 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.

Original languageEnglish (US)
Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PublisherIEEE Computer Society
Pages583-592
Number of pages10
ISBN (Electronic)0818629002
DOIs
StatePublished - 1992
Externally publishedYes
Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
Duration: Oct 24 1992Oct 27 1992

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1992-October
ISSN (Print)0272-5428

Conference

Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
CountryUnited States
CityPittsburgh
Period10/24/9210/27/92

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Efficient minimum cost matching using quadrangle inequality'. Together they form a unique fingerprint.

Cite this