I have two sets of numbers and need to find a mapping between those two sets, so that the total distance between two mapped numbers is as small as possible. Two numbers must not be mapped if they are farther apart then
0.18. As many numbers should get mapped as possible.
Also, the sets are not necessarily the same size. So, consequently, some numbers of the larger set won’t get any mapping.
Is there a reasonably efficient algorithm that finds a mapping like this? Or, is there a term for this specific problem so that I can research algorithms on my own?
Through googling I encountered this question, which led me to the term “Euclidean Bipartite Matching Problem” which seems to be the term for a problem very similar to mine. However, my problem is slightly different than the Euclidean Bipartite Matching Problem.
So basically, I’m looking for an efficient algorithm for the 1-dimensional Euclidean Bipartite Matching Problem except that the two sets of numbers can be of differing size, and the distance between two numbers must not exceed
I’ve already coded my own implementation, however… it doesn’t work properly and is pretty complicated too so that I’m not even sure why it doesn’t work.
As for the basic idea behind my implementation: let’s call the first set the red numbers and the second set the blue numbers (apparently that’s the terminology used in the Euclidean Bipartite Matching Problem). Now;
- go through all red numbers, and for each:
- find the closest blue number within a ±0.18 range
- if the blue number is already assigned to a different red number:
- if the existing assigned red number is nearer than our red number, skip this blue number
- assign our red number to the blue number
- if we overwrote a previously-assigned red number in the process, make the red number find itself a new blue number (i.e. make the red number go through steps 1-4 again)
(I’m doubtful that this implementation is even correct) but yeah, this is what I tried so far.
Are there well-known algorithms to do this task, so that I don’t have to create a wonky, non-functioning, slow implementation myself? Or in general, is there a term for this specific problem? Then I could google for that term and find what I need.
I’ll be happy about any answer or pointers 🙂