Minimum distance between sequence a and all permutations of another sequence b

If $p\ge 1$, then the minimum is attained by rearranging $b$ so that it is "order isomorphic" to $a$, meaning that $b_i-b_j$ has the same sign as $a_i-a_j$ for all $i,j$. To see this, suppose that $a_i<a_j$ and $b_i<b_j$. Using the convexity of the function $f(x)=|x|^p$, you can show that $$ |a_i-b_i|^p+|a_j-b_j|^p\le |a_i-b_j|^p+|a_j-b_i|^p $$ Therefore, if $a_i$ is matched with $b_j$ and $a_j$ with $b_i$, it is more efficient to swap $b_i$ and $b_j$. This means if $b$ is optimal, it must have no such out-of-order matching.

When $p<1$, the function $|x^p|$ is no longer convex, so the same local swapping rule does not always hold. In fact, it is sometimes reversed. Here are some observations:

• If $a_1<a_2<b_1<b_2$, then it is more efficient to match $a_1$ with $b_2$ and $a_2$ with $b_1$ (this is the opposite of the $p\ge 1$ case).

• If $a_1<b_1<b_2<a_2$, then it is more efficient to match $a_1$ with $b_1$ and $a_2 $ with $b_2$ (this is the same as the $p\ge 1$ case).

• If $a_1<b_1<a_2<b_2$, then the optimal matching depends on the values of $a_1,a_2,b_1$ and $b_2$. For example, when $a_2-b_1$ is very small, it is optimal to pair $a_1$ with $b_2$, but as $a_2-b_1$ increases to $\infty$ while $b_1-a_1$ and $b_2-a_2$ remain constant, then eventually the opposite matching is better.

I am not sure if these observations translate into an algorithm.