1
$\begingroup$

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$?

$\endgroup$

closed as off-topic by Joonas Ilmavirta, Gjergji Zaimi, Stefan Kohl, Dima Pasechnik, Ryan Budney May 12 '15 at 20:56

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Joonas Ilmavirta, Stefan Kohl, Dima Pasechnik, Ryan Budney
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    $\begingroup$ en.wikipedia.org/wiki/Hungarian_algorithm $\endgroup$ – Gerry Myerson May 12 '15 at 12:45
  • 1
    $\begingroup$ Thanks Gerry, this lead me to the right solution. There is still work there, I am basing the algorithm on this article csclab.murraystate.edu/bob.pilgrim/445/munkres.html which doesn't cope with some situations very well but it should be okay eventually. Thanks $\endgroup$ – Peter Kottas May 14 '15 at 8:13
  • 1
    $\begingroup$ Btw, thanks a lot to you guys who helped formatting the question to the proper mathematical problem. Sorry about the off-topic I'll post stuff like this directly to math.stackexchange next time. $\endgroup$ – Peter Kottas May 14 '15 at 10:46