0
$\begingroup$

I have a random binary matrix $A$

$$ A=\left[\begin{array}{c c c c c}0&0&0&0&1\\0&1&0&1&0\\1&1&1&1&0\\0&1&1&0&0\\1&0&1&1&1 \end{array}\right] $$ and a permutation of the identity matrix (denoted later as $I_p$) that will filter it. I want to find the best permutation $I_p$ (using row/column swapping) so as to maximize $\text{sum}(AI_p)$

  • $\text{sum}(AI_p)$ is computed using element-wise sum and multiplication

ex.

$$ A=\left[\begin{array}{c c c}0&1&0\\1&0&1\\1&0&0 \end{array}\right] $$

the maximum $\text{sum}(AI)$ would be from $$ I_p= \left[\begin{array}{c c c}0& 1& 0\\0& 0 &1\\1 &0& 0 \end{array}\right] $$

I am currently checking every possible column permutation of $I$, which scales terribly.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ by sum(AI), I take it that you mean the element-wise sum of the element-wise product of A and I, right? If you use conventional matrix multiplication, then AI is just a permuted version of A and the sum of the elements won't change. $\endgroup$ – Brian Borchers Jun 30 '17 at 21:44
4
$\begingroup$

This is an assignment problem. There are lots of fast algorithms for these problems. How big are your instances?

Improve this answer
$\endgroup$
2
  • $\begingroup$ arrays can be up to 100x100 $\endgroup$ – Alter Jun 30 '17 at 22:42
  • 2
    $\begingroup$ Your problems are tiny compared to the sizes of assignment problems that are frequently solved. $\endgroup$ – Brian Borchers Jul 1 '17 at 4:08

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.