8
$\begingroup$

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.

$\endgroup$

migrated from programmers.stackexchange.com Jul 2 '14 at 2:47

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

  • $\begingroup$ Not sure, but maybe this thread can be of help to you? $\endgroup$ – logc Jul 1 '14 at 15:10
  • $\begingroup$ Im very interested in this problem as I've also run into it when designing some ML algorithms... $\endgroup$ – daaxix Jul 2 '14 at 3:46
  • $\begingroup$ 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.) $\;$ $\endgroup$ – user12859 Jul 2 '14 at 6:16
  • $\begingroup$ "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? $\endgroup$ – Raphael Jul 2 '14 at 8:35
  • $\begingroup$ @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?" $\endgroup$ – Herbert Jul 2 '14 at 9:48
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\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.