# Best combination of values pulled from a matrix

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?

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.