Let's suppose that we have an $n \times n$ matrix $M$ containing only strictly positive elements $m_{ij}$. Is there a fast algorithm/procedure that finds the subset of elements $$m_{i_{\nu}j_{\nu}}$$ $$i_{\nu}=i_{\mu} \text{, } j_{\nu}=j_{\mu} \iff \nu = \mu$$ $$ \nu \in [1, n]$$ that minimizes the sum $$\sum_{\nu=1}^{n} m_{i_{\nu}j_{\nu}}$$ So with words: how can I choose $n$ elements out of a positive matrix, such that I only use one element from each row and column and the sum of these elements is minimal?

  • 2
    $\begingroup$ This is an instance of the "assignment problem"; you can use the "Hungarian algorithm" to solve it. $\endgroup$ – kimchi lover Dec 6 '19 at 19:27
  • $\begingroup$ Thank you, this is exactly what I was searching for! $\endgroup$ – fazekaszs Dec 7 '19 at 20:19

Your Answer

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

Browse other questions tagged or ask your own question.