0
$\begingroup$

we have a matrix $A=(A_{ij})^{n\times n}$ where $A_{ij}\ge0$. I want to choose $n$ numbers from this matrix(any two of the $n$ numbers are not in the same row or column, that means that in each row or column, there is only one element of the matrix is chosen) and the sum of these $n$ numbers is the maximum/minimum in all the possibilities.

For a development, we have a matrix $A=(A_{ij})^{m\times n}$ where $A_{ij}\ge0$, and $r=max(m,n)$, how to choose $r$ numbers which satisfy the conditions above?

I don't want to calculate all the possibilities with program, but a strategy to get the list of numbers the more quickly.

Thank you.

$\endgroup$
1
$\begingroup$

You are almost certainly looking for the Hungarian Method.

$\endgroup$
1
  • $\begingroup$ thank you very much. I find an approach thanks to your answer. $\endgroup$ – Martial Jan 5 '14 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.