# finding the $n$ closest pairs between $2n$ points

Given $2n$ points $x_1, x_2 \ldots x_{2n}$ and a distance $d_{i,j}$ defined between them, how can I best find the set $P$ of mutually exclusive pairs $(i,j)$ such that the sum of their distances

$$\sum_{(i,j) \in P} d_{i,j}$$

is minimised? The definition of $d_{i,j}$ is open and the function could be convex. The motivation for this problem is practical. How can I pair of 30 pictures say into most similar pairs?

I apologise in advance for the choice of tags on this post. I have been out of maths proper for a long time.

-

What you're looking for is a minimal weight perfect matching on a complete graph. From a quick wikipedia search, I think Edmonds' matching algorithm will do the trick for you (see the bottom of the page) - I think it's polynomial time in the number of nodes.

-
Many thanks for this. I think that is precisely what I need: it seems to cover the minimisation case as well as the converse maximisation. There is even some code in C++ and Python out there to do it. It also explains by my initial attempts to adapt simpler techniques failed! –  David Dec 3 '11 at 10:36

Actually, the OP is on a slightly different problem: the Euclidean minimal matching problem, where the complexity should be a lot better. See The Open Problems Project, Problem 6 (we will probably hear more from Joseph...). EDIT I also found this paper which seems to be much simpler than Edmonds, while not being particularly 2D-oriented.

-
Thanks, Igor. I will only add that there are citations under "Problem 6: Minimum Euclidean Matching in 2D" to papers that describe an exact algorithm that runs in about $O(n^{3/2})$, and $(1 + \epsilon)$ approximation algorithms. –  Joseph O'Rourke Dec 3 '11 at 13:27
Oh, I should add that the original question did not specify 2D, so perhaps these references are irrelevant... –  Joseph O'Rourke Dec 3 '11 at 14:04
In fact, the original question seems to be in a very high-dimensional space (the space of "pictures"), so this is certainly not relevant for the OP, but should be of interest to other readers of this... –  Igor Rivin Dec 4 '11 at 10:12
Although, see the edit. –  Igor Rivin Dec 4 '11 at 10:59
@Igor: I'm slightly confused about "Euclidean". The OP says that the definition of $d_{ij}$ is open, so it could be non-Euclidean too? –  Suvrit Dec 4 '11 at 11:11