Find permutation matrix that minimizes a Frobenius norm

Question

Is there an efficient way to solve (maybe approximately) the following optimization problem

$$\left\| A - X B X^T \right \|_F \xrightarrow[]{X}\min$$

where $X$ is a permutation matrix and $A$, $B$ are dense square symmetric real matrices?

Answer 1

An algorithm for this problem could be used to solve the graph isomorphism problem- let $B_{i,j}$ be 0 or 1 depending on whether or not edge $(i,j)$ is in graph $B$, and let $A_{i,j}$ be 0 or 1 depending on whether or not edge $(i,j)$ is in graph $A$. The two graphs are isomorphic if and only if there is a solution to your problem with Frobenius norm 0.

It's true that that graph isomorphism is solvable in quasi-polynomial time, but that algorithm is of more theoretical than practical interest.

Your problem is more general than the graph isomorphism problem, so I would expect it to be difficult in practice for large instances. If I had to solve it exactly for small instances, I'd probably try to develop a branch and bound algorithm. I'd try a local search heuristic for larger instances.

Answer 2

The problem is equivalent to:

$$\text{minimize} \quad \|A-XBX^T\|_F^2=\|A\|_F^2-2\langle A,XBX^T\rangle+\|XBX^T\|_F^2$$

which is equivalent to:

$$\text{minimize} \quad -\langle A,XBX^T\rangle = -\text{trace}(X^TA^TXB)$$

The latter is due to $\|A\|_F^2$ and $\|XBX^T\|_F^2$ are constants.

This problem is the quadratic assignment problem and is NP-hard, with a special case being the travelling salesman problem.