Given a real $n \times n$ matrix $A$ (feel free to assume its entries are non-negative, if it helps), what is known about the problem of computing the quantity
$$
\max\_{\sigma \in S\_n} \left\{\sum\_{j=1}^na\_{j,\sigma(j)}\right\}?
$$
(Here $S\_n$ is the symmetric group, so we are maximizing over all permutations of the columns of $A$: if you like you can write the sum as $\mathrm{trace}(AP\_\sigma)$, where $P\_\sigma$ is the permutation matrix associated with the permutation $\sigma$).


For example, is it known to be NP-hard, or is there a known polynomial-time algorithm for computing it (maybe just for certain special classes of matrices)? Does it have a name and/or is it equivalent to a well-known problem? It feels vaguely graph isomorphism-ish to me, but I'm having trouble pinning it down.


As one minor note, numerical examples show that the greedy algorithm (i.e., pick the largest entry of $A$, then forget about that row and column and pick the largest entry of the remaining $(n-1) \times (n-1)$ submatrix, and repeat) does not always produce the maximum value even if $A$ is doubly stochastic.



Maximum permuted row/column sum of a matrix
This is the maximum weight matching problem in the weighted complete bipartite graph $K\_{n,n}$, also known as the [assignment problem](https://en.wikipedia.org/wiki/Assignment_problem). It does have a few polynomial-time algorithmic solutions.


