2
$\begingroup$

Given a permutation of $n$ element and for each pair of position $i$ and $j$, a non-negative integer $c_{ij}$ which is cost of swapping $i$-th element and $j$-th element of permutation.

Is there any polynomial or pseudo-polynomial algorithm to sort the permutation with minimum cost?

$\endgroup$
  • $\begingroup$ Is this a fictional or a part of research problem? $\endgroup$ – kelalaka Oct 18 '18 at 14:11
  • $\begingroup$ It is generalized form of part of a research problem. $\endgroup$ – Reza Oct 18 '18 at 19:48

Your Answer

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

Browse other questions tagged or ask your own question.