Let say I have two $n$ x $n$ matrices $A$ and $B$ where all elements are real positive values. I want to find some $n$ x $n$ permutation matrix $P$ such that $\operatorname{tr}(P A P ^T B)$ is minimized. Does there exist such an algorithm or technique?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ How large a value of n do you need to solve? $\endgroup$– Mark L. StoneCommented Feb 13, 2022 at 16:01
-
1$\begingroup$ This looks like the quadratic assignment problem (QAP). $\endgroup$– Rodrigo de AzevedoCommented Feb 15, 2022 at 9:56
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
This problem is NP-hard.
Let $A$ be the adjacency matrix of an $n$-cycle plus the all-ones matrix and $B$ the adjacency matrix of a graph $G$ plus the all-ones matrix.
Then, if $G$ has a Hamiltonian cycle, the maximum trace is achieved when the elements of $PAP^T$ with value $2$ corresponds to a Hamiltonian cycle in $G$. Since finding Hamiltonian cycles is NP-hard, your problem is NP-hard.
answered Feb 13, 2022 at 9:49
-
$\begingroup$ Oh no! I was afraid this was the case. Your proof is very elegant so I can’t even argue with it. My only criticism is that my question was about minimizing not maximizing, but your general proof would still work in the minimizing case if you set $A$ equal to 1 - (n adjacency matrix) instead $\endgroup$ Commented Feb 13, 2022 at 20:47