The exact complexity of computing the minimum weight perfect bipartite matching in the Euclidean case is an open problem in computational geometry. This problem fits into the common theme of taking standard optimization problems on general weighted graphs and giving them a geometric flavor by forcing all the edge-weights to be Euclidean distances. Doing this often makes the problem easier to solve than the problem on general weighted graphs. Examples include minimum spanning tree (it’s open whether the Euclidean version can be done in linear time or not; the general version is known to take at least time) and the travelling salesman problem (the general version is hard to approximate, but the Euclidean case has a PTAS).

More formally, consider two sets and of points each in the two dimensional plane. This defines a complete weighted bipartite graph where we create a node for each point in and an edge for all and . To each edge , we assign a weight equal to the Euclidean distance between and . The question, then, is to compute the minimum weight perfect matching in this graph in time. Currently, the best known algorithm takes time where hides logarithmic factors. If we don’t care about the accuracy, it is possible to reach almost linear time, that is, there exists a near linear time algorithm that finds a -factor approximation for any . Getting a subquadratic approximation algorithm is a good sign because often approximation algorithms can be made exact by setting the appropriately, if we know something about the solution space. For example, if we know that the set of all possible weights achievable by a perfect matching is an integer in the range , we can get an exact solution by setting to be something slightly smaller than . Of course, this approach has obvious caveats, including a) that we do not know anything about the set of possible weights achievable by the perfect matchings and b) that setting to be a polynomial in will blow up the running time.

An interesting special case is when all the points are promised to belong to a integer grid. In this case an *additive* approximation algorithm is known that runs in time, being a small positive constant. Here the hides logarithmic factors in and and polynomial factors in . From now on, we will also hide the in the .

Being on an integer grid has some advantages. For example, the weight of a perfect matching, then, is the sum of square roots of integers, each in the range . Sums of square roots of integers are, for many reasons, very interesting for the algorithms community and thus have been studied extensively. It is known, for example, that for any two sets of integers each, the difference between the sum of square roots of the integers in one set and the sum of square roots of the integers in the other set is lower bounded by where is polynomial in but doubly exponential in . That doesn’t quite help us yet, because setting to be something doubly exponential in is horrible for the running time.

In a recent paper by R. Sharathkumar, this problem was circumvented with a clever trick and a time exact algorithm was shown for the case when points lie on a integer grid. The algorithm is really neat and works by combining a few ideas in the right way. One black box it uses is the fact that if instead of a complete bipartite graph in the two dimensional plane, you are given a planar graph, then the minimum weight perfect matching can be found using planar separators in time. Thus his main idea is that given the complete bipartite graph, extract from it a subset of edges such that a) the subset is planar and b) it contains the minimum weight perfect matching of the complete bipartite graph. He shows that such a subset can be found in time. To do this, he builds up on the additive approximation algorithm and uses the fact that sums of square roots of two sets of integers cannot be arbitrarily close to each other.