Find permutation minimizing distance

You have a square matrix of weights $W$ and a square matrix of distances $D$. You want to find a permutation $\sigma$ minimizing $$\sum_{i,j} W_{i,j} D_{\sigma(i), \sigma(j)}$$

Is there a known algorithm for that? Is the problem NP-complete? Is the optimal solution easily approximable?

• If $D_{i,j} = |i-j|$ then we get minimum linear arrangement, a well-known NP-complete problem. Dec 12 '15 at 22:17

Your problem appears to be very close to the minimum quadratic assignment problem, see for example a paper by Hassin, Levin and Sviridenko; your problem is close to the metric variant (since $D$ is a metric). When $D_{i,j} = |i-j|$ we get the NP-hard problem minimum linear assignment, whose best known approximation ratio is $\tilde{O}(\sqrt{\log n})$.