Placing n non attacking rooks on a value weighted n*n board, such that the value of the sum of the chosen squares is minimal

Question

I have a variation of the n rooks problem: https://en.wikipedia.org/wiki/Rook_polynomial

I have a weighted n*n matrix, say 4 * 4, where each "square" has a value. I would like to place n non attacking rooks, such that the sum of the squares they fall on is minimal.

Eg:

3,  4,  5, 10
1,  1,  9,  7
5,  6,  2,  8
7,  8, 12,  4

The solution to this specific example I believe is:

 3*,  4,   5,  10
 1,  1*,   9,   7
 5,   6,  2*,   8
 7,   8,  12,   4*

Where * denotes a placement of a rook.

I'm wondering if the following greedy algorithm is correct: Select the current minimal value square that is not "attacked", if there are multiple with the same shared value, tiebreak by selecting the column in which the next smallest value is greatest.

Is there a way to prove the correctness of a greedy algorithm for this problem? Are there counter examples for the greedy algorithm I described?

Thanks

Answer 1

This is the linear assignment problem, and there are polynomial algorithms to solve it. But the greedy algorithm is not guaranteed to find an optimal solution.