## Abstract

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 = 1}sj)) time, where d_{i} is the demand at the ith sink, s_{j} is the supply available at the jth source, and Σ^{n} _{i = 1}d_{i} ≤ Σ^{m} _{j = 1}s_{j}.

Original language | English (US) |
---|---|

Pages (from-to) | 116-143 |

Number of pages | 28 |

Journal | Journal of Algorithms |

Volume | 19 |

Issue number | 1 |

DOIs | |

State | Published - Jul 1995 |

Externally published | Yes |

## ASJC Scopus subject areas

- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics