4
$\begingroup$

this is my first post here so bare with me :).

What i'm looking for is an algorithm that can find the maximum sum of values in a square grid under the restriction, that you can only pick 1 value from each column and row.

so for example:

$$ \begin{matrix} 3 & 2 & 5 \\ 4 & 1 & 4 \\ 3 & 1 & 2 \\ \end{matrix} $$

in the first row, you pick 5, in the second you pick 4 and in the third you pick 1, for a total of 5+4+1 = 10.

The algorithm I came up with is similar to using Laplace expansion to find the determinant of a matrix.

(I'm using matrix and square grid interchangebly)

For every value in the first row, you recursively find the max sum of the matrix without that values' column/row and then add that result with the value. The maximum of these is our result (recursion end: 1x1 matrices return the value).

This algorithm runs in O(n!) (T(n) = n*T(n-1) for n x n square grids) and I was wondering if anyone of you can come up with a faster algorithm.

I know that there are faster algorithms for finding the determinant, such as LU decomposition O(n^3) and Bareiss' algorithm O(n^3) or fast matrix multiplication O(n^2.373), but the ones I have looked at were to confusing for me to change into a fitting algorithm for this problem.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your problem is known as the assignment problem, and can be solved efficiently.

$\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.