CODEWITHSUNDEEP
algorithmconvex-optimization
ysig
ysig

Reputation: 507

Match two sets of objects

I am trying to figure out how to solve the following problem with a program:
I have a set of objects A = [Ai] and another set of objects B = [Bj].
I also have a matrix C=[cij] calculating the similarity between A and B (which is fully dense).
I want to assign each object to a single other object (min(|A|, |B|) pairings in total) so that the sum of all the used cij is the maximum possible. (Also Cij is symmetric)

I tried to formulate it as a bipartite matching problem but I couldn't find an existing definition and implementation of what I am asking, although it looks really familiar and this is why I ask for your help.

Thank you

Upvotes: 1

Views: 155

Answers (1)

ysig
ysig

Reputation: 507

The problem is that of unbalanced assignment: https://en.wikipedia.org/wiki/Assignment_problem

There seems to be an implementation in scipy: https://docs.scipy.org/doc/scipy-0.18.1/reference/generated/scipy.optimize.linear_sum_assignment.html

that solves it. You need to convert similarities to costs (you can just take the negative).

Upvotes: 2

Related Questions