Maximize the trace of a matrix by permuting its rows

$\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

1 Answer

$\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

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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