Is there a reasonably cheap method to solve the large, dense, low rank assignment problem $\max_\pi \sum_i A_{\pi i,i}$, where $\pi$ runs over all permutations.of $1:n$?

Here $A$ is an $n\times n$ matrix of low rank $r$. Typical sizes would be $n=10000~~$ (possibly much larger), $r=15$.

  • 1
    $\begingroup$ By $\pi i$ do you mean the product so that you're striding through the matrix for different $\pi$? $\endgroup$
    – Bill Barth
    Mar 7, 2013 at 14:24
  • $\begingroup$ $\pi$ runs over all permutations. $\endgroup$ Mar 8, 2013 at 11:48
  • $\begingroup$ Shouldn't it be $A_{\pi(i),i}$ then? $\endgroup$ Mar 8, 2013 at 20:41
  • $\begingroup$ @JackPoulson: $\i(i)$ and $\pi i$ are two different notations for the image of $i$ under the permutation $\pi$. $\endgroup$ Mar 11, 2013 at 9:02
  • $\begingroup$ Interesting question! Are you looking to exploit the low-rank structure just for storage reasons---that is, to save from having to form the entire matrix when applying a traditional assignment algorithm? Or are you looking for a way to exploit the low rank to accelerate the search? $\endgroup$ Mar 22, 2013 at 16:14

1 Answer 1


Since $A=R_1R_2^T$ with $R_1, R_2\in \mathbb{R}^{n \times r}$, we have $$ \sum_i A_{\pi i, i} = \sum_i (P_{\pi} A)_{i, i} = \text{trace}(P_{\pi}R_1R_2^T) $$ where $P_{\pi}$ is the permutation matrix corresponding to $\pi$.

For any $\pi$, the trace can be computed as $$ \text{trace}(P_{\pi}R_1R_2^T) = \sum_{i} \sum_{k} (P_{\pi}R_1)_{i,k} (R_2^T)_{k,i} = \sum_{i,k} ((P_{\pi}R_1)\circ R_2)_{i,k}. $$ (This quantity is also known as Frobenius product, $P_{\pi}R_1:R_2$).

This idea doesn't take away the burden of having to go through all permutations and brute-force search for the maximum of all Frobenius products, and in fact is has the same arithmetic complexity as explicitly computing $A=R_1R_2^T$. However, it has much lower memory requirements since you never have to actually form $A$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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