I have an interesting optimization problem I am trying to solve now and I thought I d share it here in order to find the best answer. The problem itself is not complicated and it is stated like this:

Given a matrix n x m, m>n, find M index for every N index (every row can be used only once) so that sum(matrix[Ni,Mi]) is minimal. In other words : 

1 2 3 

4 5 6

6 8 9

So you might choose N0=0, M0=0, N1=1, M1=1, N2=2, M2=2 which gives 1+5+9 = 15. Now lets try N0=1, M0=0, N1=2, M1=1, N2=0, M2=2 giving 2+6+6 = 14. That is the correct answer in this case but the problem is to figure out an algorithm that can do this. The performance is an issue as well so I d like to keep it simple if possible (obviously the matrix dimensions are normally much bigger than 3x3). So far I have one solution but I am not certain if I took the best way for it. I can share it later but I don't want to mislead you now.

Any help is appreciated, thanks in advance.

Peter