Two Algorithmic Schemes for Geometric Bipartite Matching and Transportation

Thumbnail Image



Journal Title

Journal ISSN

Volume Title

Repository Usage Stats



Given n red points and n blue points in d-dimensional space and a distance function, the geometric bipartite matching problem is to find a matching of red points to blue points, such that the sum of distances between the matched pairs is minimized. The general graph problem, minimum-cost bipartite matching, can be solved in polynomial time using the classical Hungarian algorithm, which leads to a cubic algorithm for the geometric matching problem. We present several algorithms for computing optimal and near-optimal geometric bipartite matching and its fractional generalization, geometric transportation. We also present fast algorithms for partial matching, i.e., match only k pairs for a given k <= n.

Finally, we consider the case when red points are allowed to translate (rigidly) and the goal is to find a partial matching minimum-cost matching under all translations of red points. We assume the cost of a matching to be the sum of squares of edge costs (RMS). For a given translation t, let f(t) denote the cost of optimal partial matching (for a fixed k). A long-standing open problem is whether the number of local minima in f(t) is polynomial; the best upper bounds are exponential. We show that there is an approximation g(t) of the function f(t) that has only quadratic number of local minima.





Xiao, Allen (2020). Two Algorithmic Schemes for Geometric Bipartite Matching and Transportation. Dissertation, Duke University. Retrieved from


Dukes student scholarship is made available to the public using a Creative Commons Attribution / Non-commercial / No derivative (CC-BY-NC-ND) license.