Welcome to MathOverflow

Question

6

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.

edited Dec 3 2011 at 0:46

Anthony Quas
6,260●1●12●28

asked Dec 3 2011 at 0:31

David
63●2

Anthony Quas · Accepted Answer · 2011-12-03 01:26:25Z UTC

6

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.

edited Dec 3 2011 at 1:26

answered Dec 3 2011 at 0:45

Anthony Quas
6,260●1●12●28

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 2011 at 10:36

Igor Rivin · Answer 2 · 2011-12-04 11:01:11Z UTC

6

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.

edited Dec 4 2011 at 11:01

answered Dec 3 2011 at 10:38

Igor Rivin
31.1k●3●37●71

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 2011 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 2011 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 2011 at 10:12

Although, see the edit. – Igor Rivin Dec 4 2011 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? – S. Sra Dec 4 2011 at 11:11

show 2 more comments

finding the $n$ closest pairs between $2n$ points

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.