I came across a problem which I think can be reduced to the assignment problem/Hungarian algorithm.

We have matrix $A$ and matrix $B$ which are both $n\times n$ symmetric matrices. We can rearrange $B$ in the following manner: column $i$ can be swapped with column $j$ provided that next, row $i$ is swapped with row $j$. This preserves the symmetry of $B$.

The problem statement is to find a rearrange of $B$ in this manner which minimizes the Frobenius norm of $A-B$.

Any guidance on an approach would be greatly appreciated. Thank you very much in advance.



Your Answer

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