# Find the smallest summed distances by uniquely pairing elements of one set to elements of another set

As input I have two sets of points in RN, typically for large N, for example N=40. Supose both sets have m elements:

S = s1 ... sm

T = t1 ... tm

Semantically both sets are equal, but due to noise (of whatever kind) on the R^N points, elements which should be semantically the same still have a distance larger than 0.

What I want to find is m tuples (si, tj) such that the sum of distance(si, tj) is minimized and such that sk and tk exactly occur once in the set of tuples for k=1...m. Basically (i,j) have to be chosen as towers on a chessboard which can not hit each other while minimizing the summed distances.

In other words, I want to find an onto one-one map between S and T which 'is sort of an identity map, but robust to noise'. We assume that the distance measure is a good indication of how similar elements are.

Basically I need to find a permutation of 1...N, and hence I think this problem is either NP-hard or NP-complete, since it 'feels' quite similar to the TSP; however I have not been able to rewrite the TSP problem to a subset of my problem here.

Is this problem realistically solvable for large N? Is there a name for this problem? What would be a feasible solution? Is there another criteria which might be better than the summed distances?

I thought of a greedy approach, let D be a matrix of the distances, dij = distance(si, tj).

T = {}
while D is not empty:
(i,j) = argmin-(i,j) dij
append (i,j) to T
set row i and column j to infinity.


This does not result in the optimal solution, but finds a solution. Would this be my best bet? Should I use simulated annealing, or is it overkill?

PS: from my point of view, this is just a minor problem in a bigger ML problem, however, I am very much interested in the CS background of it.

## migrated from programmers.stackexchange.comJul 2 '14 at 2:47

This question came from our site for professionals, academics, and students working within the systems development life cycle.

• Not sure, but maybe this thread can be of help to you? – logc Jul 1 '14 at 15:10
• Im very interested in this problem as I've also run into it when designing some ML algorithms... – daaxix Jul 2 '14 at 3:46
• I can't see any way to avoid solving the sum-of-square-roots problem as part of this problem. $\hspace{.75 in}$ (I also don't see any argument that this problem is SoSR-hard.) $\;$ – user12859 Jul 2 '14 at 6:16
• "Basically I need to find a permutation of 1...N, and hence I think this problem is either NP-hard or NP-complete" -- just like sorting, hm? – Raphael Jul 2 '14 at 8:35
• @Raphael: Good point. It was more a gut-feeling, which like stated in the OP I can not find arguments for. Hence the question "Is this problem realistically solvable for large N?" – Herbert Jul 2 '14 at 9:48

This is the problem of finding the maximum matching in a weighted bipartite graph. There are efficient algorithms that solve this problem in polynomial time.

Basically, you have a complete bipartite graph with $2m$ vertices. $S$ forms one set of vertices; $T$ forms the other set of vertices. For each $i,j$, create an edge from $s_i$ to $t_j$ whose weight is equal to $-d(s_i,t_j)$, the negation of the distance between $s_i$ and $t_j$.

Now, you want to find a matching whose weight is as large as possible. This corresponds to a set of pairs $(s_i,t_j)$ whose total distance is as small as possible. From there, you can use existing algorithms on this graph to find the maximum-weight matching.

Here's a quick probabilistic method that might work for you.

1. Project your points onto a random line and solve the 1D matching problem in this line.

2. Repeat the process for a handful of different random lines to get a collection of candidate matchings.

3. Have your candidate matchings "vote" point by point to come up with the "best" matching.