Minimizing the distance of pairing points

Question

My problem is as follows:

Given a number of 2n points, I can calculate the distance between all points 
and get a symmetrical matrix.

Can you create n pairs of points, so that the sum of the distance of all pairs is 
minimal?

EDIT: Every point has to be in one of the pairs. Which means that
every point is only allowed to be in one pair.

I have naively tried to use the Hungarian algorithm and hoped that it may give me an assignment, so that the assignments are symmetrical. But that obviously did not work, as I do not have a bipartite graph.

After a search, I found the Stable roommates problem, which seems to be similar to my problem, but the difference is, that it just tries to find a matching, but not to try to minimize some kind of distance.

Does anyone know a similar problem or even a solution? Did I miss something? The problem does actually not seem that difficult, but I just could not come up with an optimal solution.

Answer 1

There's a primal-dual algorithm due to Edmonds (the Blossom algorithm), which you really don't want to implement yourself if possible. Vladimir Kolmogorov has an implementation that may be suitable for your purposes.