# 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.

• 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
• @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
• I thought it was euclidean because he said "points", but you may well have a point... – Igor Rivin Dec 4 '11 at 12:08
• It will most likely be Euclidean but in $R^6$ or $R^8$. However this is very much an applied problem, so if the general method works, that will be fine too. Its good to know that the other work exists: one never knows when one will need it. – David Dec 5 '11 at 12:53