0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Mar 5 '18 at 20:46
  • $\begingroup$ 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. $\endgroup$ – bebbi Mar 5 '18 at 20:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ no more than one upvote at my disposal :( $\endgroup$ – bebbi Mar 6 '18 at 10:21
  • $\begingroup$ A note for others: while hungarian is nxn, it's possible to fill the set with a smaller item count with dummy items that have unfavorable connections. And turn cost into profit problem by subtracting numbers from the highest occurring number. $\endgroup$ – bebbi Mar 6 '18 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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