I have given matrix with size $n$ by $m$,such that $n<100, m<15$, for example here is matrix with size $n=3, m=2$

$\begin{pmatrix}3&0\\ 6&9\\ 5&9 \end{pmatrix}$

Now for this matrix we want to find the minimum sum such that we should pick exactly one element from each column and we should pick elements that are in same row.

For example we can pick 3+9, or 6+0, 5+0, but we cannot pick 3+0 or 6+9. I was searching over the net and found out for Hungarian algorithm, but it works if we should take one element from each row and column, and here we have 100 rows and we should take only 15 of them in worst case.

Which algorithm should i use, any hints?

  • $\begingroup$ You are basically describing the Linear Assignment Problem. You can still use the Hungarian method here, you just need to add in dummy entries that are greater than the current maximum entry to produce a square matrix. $\endgroup$ – GEL Mar 26 '17 at 14:35
  • $\begingroup$ Do you want to say that i should fill the other part of the matrix to make it with size $n$ by $n$, but then I will search over all combinations with size $n$ by $n$ and i won't get correct result? $\endgroup$ – someone123123 Mar 26 '17 at 14:42
  • $\begingroup$ Which you should use? Rather difficult to say. Depends a lot on computational and memory capabilities on the device you plan to solve it on, speed requirements on running the algorithm. Time allowed for implementation and QA and how large the risk of needing to add any other functionality in the future is. $\endgroup$ – mathreadler Mar 26 '17 at 15:19
  • $\begingroup$ I wont need to add any other functionality in the future, also i have 1 second allowed time limit. $\endgroup$ – someone123123 Mar 26 '17 at 16:43
  • $\begingroup$ Yes, if you fill out with values greater than matrix maximum, then you'll get the results you're looking for. An efficient C implementation (implemented by you of course) of the Hungarian method can process 1000x1000 matrices in under a second on modern hardware. Your 100x100 matrix should be trivial to process. $\endgroup$ – GEL Mar 26 '17 at 17:45

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.