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

Question

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

S = s₁ ... s_m

T = t₁ ... t_m

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 (s_i, t_j) such that the sum of distance(s_i, t_j) is minimized and such that s_k and t_k 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, d_ij = distance(s_i, t_j).

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.

Answer 1

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.

Answer 2

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.