Efficient algorithm to map two differently-sized sets of numbers as closely as possible?

Question

The problem

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.

Example:

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?

My research

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 0.18.

My attempt

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;

1. go through all red numbers, and for each:
   1. find the closest blue number within a ±0.18 range
   2. 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
   3. assign our red number to the blue number
   4. 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 :)

Answer 1

This can be solved by reduction to the unbalanced assignment problem.

Build a bipartite graph where the vertices are the two sets of numbers, and there is an edge from a vertex in one set to a vertex in the other set if and only if the distance between the numbers is less than or equal to 0.18. Set the weight of each edge to the distance between the two numbers.

The goal is to find a minimum-weight maximum bipartite matching in this graph. Some minimum-weight bipartite matching implementations will do this directly.

If you only have access to an implementation that requires a fixed output matching size, you can still solve this by adding extra edges with arbitrarily huge weights (any value larger than 0.18 times the size of the smaller vertex set) to make a complete bipartite graph. Then throw out any mappings in the output that have the arbitrarily huge weights. This works because the minimum weight guarantee ensures that as few as possible of the edges with arbitrarily huge weights will be chosen in the output assignment.