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 \geq n$) matrix $A$, find $M$ index for every $N$ index (every row can be used only once) so that $\sum_iA_{N_i,M_i}$ is minimal.
To clarify with an example: $$ \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
More concisely:
What is the best algorithm that finds solution of the following optimization problem $$ \min_{\sigma:[n] \to [m]} \sum_i^n A_{i,\sigma(i)} $$ for an arbitrary $n\times m$ matrix $A$, where $m \geq n$?
