Maximize the trace of a matrix by permuting its rows

I have been struggling with a combinatorial problem that eventually translates to the following:

Given an $n \times n$ nonnegative matrix, find a permutation of the rows that maximizes the trace.

I could compute all $n!$ permutations and find the one that maximizes the trace, but that is not computationally efficient. What is the most efficient way of accomplishing this?

If it helps, this is the same as finding $n$ entries of the matrix with no two of them in the same row or column, so that the sum of these entries is maximal.

• A greedy solution: find $(i_1,j_1)=\operatorname{arg\,max} A_{ij}$, then for each remaining $k=2,\ldots,n$, $(i_k,j_k)=\operatorname{arg\,max} A_{ij}$ over $i\not\in\{i_1,\ldots,i_{k-1}\}$ and $j\not\in \{j_1,\ldots,j_{k-1}\}$. Now permute $A$ so that row $i_k \to j_k$ is moved to $j_k$. I suspect this is optimal but I haven't proved it. The computational complexity is $n^2 + (n-1)^2 + \dots + 1^2 = \tfrac{1}{6}n(n+1)(2n+1) = \mathcal{O}(n^3)$ Aug 9 '18 at 0:15
• Non-greedy solution: This problem is $\operatorname{maximize} \text{tr}(P A)$ over permutation matrices $P$. This is non-convex but we can compute an upper bound (that could potentially be pretty good or correct) by instead maximizing the same $\operatorname{maximize} \text{tr}(P A)$ over the convex hull of the set of permutation matrices, the Birkhoff polytope, the set of doubly stochastic matrices. In theory this is a linear program, and can be solved in polynomial time $\mathcal{O}(n^3)$ time by representing the constraint well. Aug 9 '18 at 0:22
• The greedy solution does not give the best answer. Here is an example why: $A = [3, 5; 0, 3]$. Aug 9 '18 at 4:26
• oh! Actually I think we do know the objective is maximized at the corners precisely because the objective is linear, and linear programs always have a maximum at the vertices (use simplex algorithm, for example)! So the non-greedy solution would work. I’ll write up an answer tomorrow I guess :) Aug 9 '18 at 7:22
• @Keivan On using LP, take a look at this. Aug 9 '18 at 7:28