Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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
1  
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
1  
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
1  
@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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.