# Maximum permuted row/column sum of a matrix

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.

This is the maximum weight matching problem in the weighted complete bipartite graph $$K_{n,n}$$, also known as the assignment problem. It does have a few polynomial-time algorithmic solutions.