2
$\begingroup$

I am trying to figure out how to solve the following problem: I have 2 sets of objects, set A and set B. I have a metric that calculates how closely a given object from set A corresponds to an object from set B. I'd like to maximize the overall correspondence of the entire set.

What I tried first was a sort of greedy algorithm, where I went through each object in set A and calculated that object's correspondence with each object remaining in set B. I then replaced the object in set B that had the highest correspondence with the object in set A. For the next object in set A, I did the same thing, leaving out the objects in set B that already had a correspondence.

The problem with this approach is that it works very well for the first part of the sets, but as I near the end, there are fewer objects in set B to match with, so objects from set A tend to have worse correspondence with those objects.

I think that it might be better to do a full calculation of the correspondence of each item in Set A to each item in Set B, and from there choose each item from set A that has the highest correspondence of the next item in set B.

However, I'm left wondering if you could have a situation where, for example, object 1 from set A has, let's say an 95% correspondence to object 6 in set B, but it's next best correspondence is only 50% with object 14 in set B. Meanwhile, object 2 from set A has a correspondence of 97% to object 6 from set B, but it has a 96% correspondence to object 28 in set B. In my mind, I think it would be better for object 1 from set A to be matched with object 6 from set B (95% correspondence) and object 2 from set A to be matched with object 28 (96% correspondence) in set B instead of matching object 2 in set A to object 6 in set B and object 1 in set A to match object 14 in set B.

Is there a name for such an algorithm? I feel like it's related to the Knapsack Problem, but is not exactly the same. There will always be the same number of objects in set A and set B. I suppose it's possible that there will be more than 1 set of mappings that are "most optimal". In that case, I don't care which one is chosen.

In my application there will be between a few hundred to 10 or 20 thousand objects in each set. The average will probably be around 5,000 or so.

$\endgroup$

1 Answer 1

2
$\begingroup$

This is known as the assignment problem. There are polynomial-time algorithms for it.

$\endgroup$
1
  • $\begingroup$ Thank you! I've never heard of that before, but it definitely looks useful! $\endgroup$ Mar 18, 2017 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.