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

• @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
• 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