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.



finding the $n$ closest pairs between $2n$ points
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](http://en.wikipedia.org/wiki/Edmonds%27s_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.


