Given a matrix $A_{n\times n}$ of real numbers, what fast algorithms do there exist to compute the maximum value of $a_{1,\sigma(1)}+a_{2,\sigma(2)}+\ldots+a_{n,\sigma(n)}$ over all permutations $\sigma$ of $1,2,\ldots,n$?
Brute-force would take $O(n!)$ time.
Is there a name to this problem/algorithm?
On
Your problem is identical to computing the so-called "permanent" of a matrix, just over a different semi-ring, namely if you define multiplication to be addition and you define addition to be $\max$. Thus any faster than $O(n!)$ algorithm for computing the permanent will work for your problem, as long as additive-inverses aren't needed (because there is no inverse for $\max$). Also, if you are only using the operations $\max$ and addition to come up with an algorithm, then that algorithm could be used to compute the permanent. So it's unlikely that you'll find any polynomial time algorithm to compute your quantity, because computing the permanent is a $\#P$-hard problem.
This problem is exactly the assignment problem and can be solved in $O(n^4)$ using the well known Hungarian Algorithm. See this note for a presentation of the algorithm.
The matrix $A$ can be thought of as the biadjacency matrix of a complete bipartite graph and you simply have to find the maximum weight perfect matching in this graph.
Also note that there is another way to solve this problem by reducing it to maximum weight cycle cover (which I presented earlier). But that is not a very clean approach. See the edit history of this post for more details about that.