Given a matrix $M\in\mathbb{N}^{n\times n}$, let $Z$ be the set of all the $M$'s entry subsets $S$ such that (i) no two entries of $S$ are on the same row or column of $M$ and (ii) $|S|=n$. Clearly we have $|Z|=n!$.

Question: How can we (efficiently) find the $M$'s entry subset $S^* \in Z$ whose element sum is the smallest over all the $M$'s entry subsets belonging to $Z$?

We are interested in finding one of $Z$'s element attaining the minimum of the above question when it is not unique. Furthermore, even a method to (efficiently) obtain just the sum of the elements of $S^*$ (without necessarily finding $S^*$) would be a significant result.

Given a matrix $M\in\mathbb{N}^{n\times n}$, let $Z$ be the set of all the $M$'s entry subsets $S$ such that (i) no two entries of $S$ are on the same row or column of $M$ and (ii) $|S|=n$. Clearly we have $|Z|=n!$.

Question: How can we (efficiently) find the $M$'s entry subset $S^* \in Z$ whose element sum is the smallest over all the $M$'s entry subsets belonging to $Z$?

We are interested in finding one of $Z$'s element attaining the minimum of the above question when it is not unique. Furthermore, a method to (efficiently) obtain just the sum of the elements of $S^*$ (without necessarily finding $S^*$) would be a significant result.