9
$\begingroup$

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.

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – David Dec 3 '11 at 10:36
10
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Oh, I should add that the original question did not specify 2D, so perhaps these references are irrelevant... $\endgroup$ – Joseph O'Rourke Dec 3 '11 at 14:04
  • 1
    $\begingroup$ 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... $\endgroup$ – Igor Rivin Dec 4 '11 at 10:12
  • 1
    $\begingroup$ @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? $\endgroup$ – Suvrit Dec 4 '11 at 11:11
  • 1
    $\begingroup$ I thought it was euclidean because he said "points", but you may well have a point... $\endgroup$ – Igor Rivin Dec 4 '11 at 12:08
  • 1
    $\begingroup$ 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. $\endgroup$ – David Dec 5 '11 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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