2
$\begingroup$

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?

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.