Two Algorithmic Schemes for Geometric Bipartite Matching and Transportation

Abstract

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.