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.
Best Answer
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.