Let A and B be matrices. The aim is to maximize over all permutations of . The paper defines a simple ‘greedy’ algorithm that constructs a permutation that gives a large . Assuming that the entries of A are i.i.d. with a symmetric distribution, and that the entries of B are independent of A, it shows under some weak moment conditions , where the constant k does not depend on m. This contrasts with the fact that with overwhelming probability.
