12
$\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$
10
  • 2
    $\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, 2018 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, 2018 at 0:22
  • 3
    $\begingroup$ The greedy solution does not give the best answer. Here is an example why: $A = [3, 5; 0, 3]$. $\endgroup$
    – K1.
    Aug 9, 2018 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, 2018 at 7:22
  • 1
    $\begingroup$ @Keivan On using LP, take a look at this. $\endgroup$ Aug 9, 2018 at 7:28

1 Answer 1

8
$\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$
1
  • $\begingroup$ Ah, thanks, that seems to be exactly what I need. $\endgroup$
    – K1.
    Aug 9, 2018 at 17:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .