Find permutation matrix that minimizes a Frobenius norm 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?
 A: 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.  
A: 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.
