2
$\begingroup$

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!

$\endgroup$
  • 4
    $\begingroup$ If $d$ can be arbitrary, there is little hope. You have to try all $n!^2$ pairs of permutations. $\endgroup$ – Yuval Filmus Oct 17 '16 at 21:40
  • 2
    $\begingroup$ 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/… $\endgroup$ – D.W. Oct 17 '16 at 21:50
  • 1
    $\begingroup$ If $d$ is the Manhattan distance, or $L_1$, it looks like optimal matching to me. $\endgroup$ – Hendrik Jan Oct 17 '16 at 23:17
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice. Having proposed a general approach, I didn't think if there is a simpler one for Lp metric. $\endgroup$ – Ivan Smirnov Oct 31 '16 at 3:01
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.