Two lists $A$ and $B$ contain equal number of elements. List $A$ is in ascending order. List $B$ is randomly ordered.
$$ A = \{a_1, ..., a_N\}, a_i \leq a_{i+1} $$ $$ B = \{b_1, ..., b_N\} $$
What is an efficient algorithm to find the permutation of $B$ for which $|B-A|_1$ or $|B-A|_2$ is minimum?
If the solution to the above problem is simply the ascending order of $B$, then it is trivial to use any sorting algorithm to find the solution. But I am stuck at establishing whether it is true for lists of any arbitrary length.
Longer than a comment. In this question it was about the $l^1$ distance. The Hungarian algorithm was suggested. I was thinking that naively one could try to minimize $$\sum c_{ij} a_{ij}$$ where $c_{ij}$ positive are the given costs and $(a_{ij})$ vary over the doubly-stochastic matrices. Then we could do linear programming and get a solution at an extreme point of the polytope of doubly stochastic matrices, which will be a permutation matrix. But it seems the H alg beats this naive approach.
$\bf{Added:}$ As Rob Pratt indicated, for $l^2$ the best matching is order preserving. Same for $l^1$, I sketched a proof in the comments to my posting. Interesting for other $l^q$ norms.