Finding The Max of sum of elements in matrix in distinct rows and columns

Question

Hi,

I have a nxm matrix and I need to find the maximum of sum of its values in distinct rows and columns.

For example considering the following Matrix:

      m1 m2 m3
n1    1  2  3
n2    4  5  6
n3    7  8  9
n4    10 11 12

The max will be 12+8+4 = 24

Note that finding the max and eliminating all values belonging to that column or row is not a good solution as it doesn't work for all cases.

The exception for above will be the following:

     m1  m2
n1   17  1
n2   18  15 

If you find 18 and remove 17 and 15, the sum will be 18+1 = 19. while 17+15 = 32 has a higher value.

Any idea about the algorithm for this question?

Answer 1

The solution is to use Hungarian Algorithm. It's a complicated algorithm. There's a very good lecture on that on youtube:

http://www.youtube.com/watch?v=BUGIhEecipE