Efficient minimum cost matching and transportation using the quadrangle inequality

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

Research output: Contribution to journalArticlepeer-review

16 Scopus citations


We present efficient algorithms for finding a minimum cost perfect matching, and for serving the transportation problem in bipartite graphs, G = (Sinks ⋃ Sources, Sinks × Sources), where |Sinks| = n, |Sources| = m, n ≤ m, and the cost function obeys the quadrangle inequality. First, we assume that ah the sink points and ah the source 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 Karp and Li (Discrete Math.13 (1975), 129-142). 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 Karp and Li. 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 sink points lie on one straight line and the source 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(Σm j = 1sj)) time, where di is the demand at the ith sink, sj is the supply available at the jth source, and Σn i = 1di ≤ Σm j = 1sj.

Original languageEnglish (US)
Pages (from-to)116-143
Number of pages28
JournalJournal of Algorithms
Issue number1
StatePublished - Jul 1995
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


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

Cite this