2
$\begingroup$

Given two ordered sets $X, Y$ each containing $m$ elements in $\mathbb{R}^n$, I'm looking for a permutation $\sigma$ of the second set that minimizes

$$\sum_{i=1}^m \lVert X_i - Y_{\sigma(i)} \rVert$$

In other words, I have two sets of points in $n$-dimensional space and I want to pair off points from these sets such that the total sum of distances between the members of each pair is small. Another question on this site covers the case where $n=1$, where you can get the best possible result by simply sorting $X$ and $Y$, but I'm interested in $n>1$.

I've used a Nearest-Neighbors library to code a greedy approach that first assigns every point to its closest neighbor in the other set, and then repeats on the parts of the set that are "left behind" until all points are paired off. This does better than random permutations, but not as good as brute-force optimal solutions on small toy datasets. I've got a gut feeling that this is probably related to an existing NP-hard problem but I can't figure out how to express it in terms of anything that I've heard of.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.