In two sets, identify set of pairs with maximal sum of connections

Question

Given two sets of items

$A = { a_1, .., a_N }, B = { b_1, .., b_M },$

and assuming a connection weight $w{_i}_j \ge 0$ between any possible pair $(a_i, b_j)$ that contains one item of each set, how can I identify the set of pairs $S$ that maximizes the sum of all involved weights: $\sum_{S}w{_i}_j$, under the condition that any $a_i$ and any $b_j$ occurs maximally once in the new set?

Example: With $A = [a_1, a_2], B = [b_1, b_2, b_3]$, and

$w$'s from $a_1$ to $B$: $[5, 2, 1]$

$w$'s from $a_2$ to $B$: $[1, 0.2, 0.4]$

the solution is to use the pairs: $(a_1, b_1), (a_2, b_3)$ which result in the highest possible sum $5.4$, and $b_2$ is left over.

Also, is there a way to approximate the sum e.g. not optimizing further for those $w{_i}_j < threshold$?

I'm sure this problem has a name, but I'm not able to figure it out.

Answer 1

This is the assignment problem. There are standard algorithms, such as the "Hungarian algorithm".

If you want to only include edges whose weight is below some threshold, delete those edges first before running the algorithm.