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!
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.

The key proof is done in https://math.stackexchange.com/questions/1984686/is-x-1-y-2px-2-y-1p-ge-x-1-y-1px-2-y-2p-for-any-0-le-x-1-le.

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.