# Anyone knows an algorithm that finds minimum distance for all permutations?

Let $A$ and $B$ be two finite sets of the same size $n$. Let $P(A),P(B)$ be the set of all permutations of $A,B$ respectively. A distance function $d(a,b)$ is defined for any $a\in P(A),b\in P(B)$. We want to find $\min \{d(a,b):a\in P(A), b\in P(B)\}$ (note: $d$ is fixed).

For example, suppose we have two sets $\{1,2\}$ and $\{3,4\}$, and the distance $d$ is Euclidean distance, then all possible distance values are

$d((1,2),(3,4)) = \sqrt8$

$d((1,2),(4,3))=\sqrt {10}$

$d((2,1),(3,4)) = \sqrt{10}$

$d((2,1),(4,3)) = \sqrt{8}$

So the minimum value is $\sqrt 8$.

I think this is a very common problem so there should be some known algorithm out there. Anyone knows an efficient algorithm to solve this problem and help provide the name or reference? Thank you!

• If $d$ can be arbitrary, there is little hope. You have to try all $n!^2$ pairs of permutations. – Yuval Filmus Oct 17 '16 at 21:40
• The answer will depend on what distance function $d$ you define for $a \in A, b \in B$. Is $d$ fixed? If so, what $d$ are you using? If it's not fixed but is part of the input to the algorithm, how is it specified? If $d$ is Euclidean distance, look at en.wikipedia.org/wiki/Nearest_neighbor_search, including en.wikipedia.org/wiki/… – D.W. Oct 17 '16 at 21:50
• If $d$ is the Manhattan distance, or $L_1$, it looks like optimal matching to me. – Hendrik Jan Oct 17 '16 at 23:17

Surprisingly, if the distance is $L_p$, or the $p$-norm induced metric, then you simply sort $A$ and $B$ respectively, and then compute their distance, and that distance will be guaranteed minimal over all permutations. That is time complexity of $O(n\log n)$ and I believe it is the most efficient one.

Sometimes, before setting out to find an "efficient" algorithm, it might be a good practice to first think of proving the "greedy" algorithm is not right; because if the greedy indeed works, all efforts to search for the "efficient" algorithm will be in vain.

• Very nice. Having proposed a general approach, I didn't think if there is a simpler one for Lp metric. – Ivan Smirnov Oct 31 '16 at 3:01
• What should I do if the values in the set are not 1 dimensional? Sorting and then compute their distance doesn't seem to work. – user3667089 Sep 11 '19 at 22:51

If your weight function is just sum of pairwise distances between elements (or a monotone function of it) than this problem is reduced to the assignment problem. Most reasonable metrics (including $L_p$ for all $p$, which, in case, include Euclidean metric) satisfy this constraint. If so, we are only interested which pairs of elements are matched.

Let $a_{ij}$ be the cost of matching between $i$-th element of the first set and $j$-th element of the second set. Having the matrix $A$, you need select $n$ elements in it such that each column and each contain exactly one element and the sum of corresponding $a_{ij}$.

This is a classical problem, called assignment problem, which is effectively solved in $O(n^3)$ with Hungarian algorithm.

As far as I know, there are faster solutions ($O(n^{2.5})$ maybe), but I'm not sure. You can search for the min-cost max-flow algorithms which solve more general task and probably are being researched wider.