1

I am looking for a way to solve an assignment problem, but I am having some problems finding the correct algorithm to use.

I have 2 list of nodes A and B, and in my problem may the length of A not be equal to B.

In addition, the node a in A may not be a potential match with all nodes in B. The preference is given by a double where 0 is not interested to 1 that is very interested and then remove all matches with an edge of 0 after (As there might be matches that is impossible).

If a have a preference of x to b, will b have the same preference to a.

Example graph: Example graph

I am interested in creating the most optimal matching, meaning that to sum of the edges are the largest possible. In the example above would I be interested in the matching (1,1) and (3,2) leaving 2 in the left row unmatched, with a total edge weight of 1.9.

I have been looking at the stable marriage and the Hungarian algorithm but both these algorithm requires there to be an equal amount of nodes on each side, and they do not find the greatest total edge weight.

(Greatest or lowest is fines as I can just invert the edge weight)

Can any of you point me towards an algorithm that will solve this problem for me?

Improve this question

1 Answer 1

Reset to default
1

You can add dummy nodes to B having edges with weight 0 to nodes in A and then invert the weights of edges. Check http://en.wikipedia.org/wiki/Assignment_problem and I think you can apply Hungarian algorithm to this problem with the modification and after finding the minimum total cost you can invert the weights again.

Improve this answer
1
  • Yeah i where thinking of doing this, but would have hoped there where a more optimized algorithm for my case where there are multiple constraints. I am going to wait accepting your answer until i see if any other answers is coming.
    – Androme
    Jun 15, 2014 at 8:12

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.