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

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.

• I don't understand you mean by the set $S$. What are the elements of $S$? Is $S$ a set of pairs? A set of items? Something else?
– D.W.
Mar 5, 2018 at 20:46
• I am pairing up arbitrary items from A and B, and this group of pairs becomes my new set S. Yes, it is a set of "arbitrary" pairs from A and B. Now there could be many different ways to pair items from A and B and make up the new set S, but I'm looking for the one that has the highest sum of connection weights. Mar 5, 2018 at 20:54