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?
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})$.