Krdytkyu

Let $a$ and $b$ be finite sequences of length $n$, i.e. $a=(a_1,a_2,...,a_n), b=(b_1,b_2,...,b_n)$. I want to calculate the minimum of the distances (in an Lp norm) between $a$ and all permutations of $b$. Let $Pi_n$ be the space of all permutations of $n$ numbers, then I am looking for

$d = text{min}_{piinPi_n} ||a - (b_{pi(1)},b_{pi(2)},...,b_{pi(n)})||_p$

Is there an efficient method or optimization algorithm (something better than trying out all $n!$ permutations of b) to calculate $d$ and find the corresponding permutation $pi$?

If $pge 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|^ple |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 $pge 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 $pge 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.

An attempt to prove the inequality from Mike's answer. Feel free to correct this proof or fill in any gaps; I suspect that it's flawed.

Claim: if $a_1<a_2$ and $b_1<b_2$ are positive reals and $f$ is a non-negative, increasing, convex function over $[0,infty)$, then
$$
f(|a_1 - b_1|) + f(|a_2 - b_2|) leq f(|a_1 - b_2|) + f(|a_2 - b_1|)
$$

Proof: We note that $g(x) = f(|x|)$ is convex over $Bbb R$. So, for any $k>0$ and $a,b in Bbb R$, we have
$$
f(a - k) + f(b+k) geq f(a) + f(b)
$$
(This step seems shaky. I think this holds if $aleq b$ but not in general, which means that perhaps the rest of the proof needs to be broken into several cases)

It follows that
$$
f(|a_1 - b_2|) + f(|a_2 - b_1|) = \
f(|(a_1 - b_1) - (b_2 - b_1)|) + f(|(a_2 - b_2) + (b_2 - b_1)|) =\
g((a_1 - b_1) - (b_2 - b_1)) + g((a_2 - b_2) + (b_2 - b_1)) geq\
g(a_1 - b_1) + g(a_2 - b_2) = \
f(|a_1 - b_1|) + f(|a_2 - b_2|)
$$
as desired.