11
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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)$ $\endgroup$ – cdipaolo Aug 9 '18 at 0:15
  • 2
    $\begingroup$ 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. $\endgroup$ – cdipaolo Aug 9 '18 at 0:22
  • 1
    $\begingroup$ The greedy solution does not give the best answer. Here is an example why: $A = [3, 5; 0, 3]$. $\endgroup$ – Keivan Aug 9 '18 at 4:26
  • 1
    $\begingroup$ 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 :) $\endgroup$ – cdipaolo Aug 9 '18 at 7:22
  • 1
    $\begingroup$ @Keivan On using LP, take a look at this. $\endgroup$ – Rodrigo de Azevedo Aug 9 '18 at 7:28
7
$\begingroup$

I commend to you the Hungarian method. It's an algorithm that I'm not up to writing out here, but it's available in many combinatorics, discrete math, and graph theory textbooks, also many places on the web: Wikipedia in particular will get you started.

$\endgroup$
  • $\begingroup$ Ah, thanks, that seems to be exactly what I need. $\endgroup$ – Keivan Aug 9 '18 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.