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 an $n \times m, m>=n$ matrix, find $M$ index for every $N$ index (every row can be used only once) so that $\sum(\text{matrix}[N_i,M_i])$ is minimal. In other words : $$ \begin{pmatrix} 1&2&3\\4&5&6\\6&8&9\end{pmatrix} $$ So you might choose $N_0=0,\; M_0=0,\; N_1=1,\; M_1=1, \; N_2=2, \; M_2=2$ which gives $1+5+9 = 15$. Now lets try $N_0=1,\; M_0=0,\; N_1=2,\; M_1=1,\; N_2=0,\; M_2=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 $3\times 3$). 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