1
$\begingroup$

What is the fastest way to select $n$ values from an $n$ by $n$ matrix such that each value comes from a different row and column and the sum of those n values is minimized?

For example, given the matrix:

$$A=\begin{bmatrix}0 & 1 &5 \\1 & 4 & 3\\2 & 7 & 0\end{bmatrix}$$

The solution is $\{A_{1,2}, A_{2,1}, A_{3,3}\}$, taking 1 from the first row, 1 from the second row, and 0 from the third row.

In the brute-force case, there are $n!$ possible solutions that have to be analyzed, so the ovreall running time is $O(n!)$, although are there any faster algorithms to solve this?

$\endgroup$
2
$\begingroup$

It looks like the assignment problem, and it could be solved in $\mathcal O(n^3)$ using the Hungarian algorithm. In your case the $A$ is the cost matrix and the sum you are looking for is cost in the terms of algorithm.

$\endgroup$

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.