  We address the problem of finding the minimum decomposition of a permutation
in terms of transpositions with non-uniform cost. For arbitrary non-negative
cost functions, we describe polynomial-time, constant-approximation
decomposition algorithms. For metric-path costs, we describe exact
polynomial-time decomposition algorithms. Our algorithms represent a
combination of Viterbi-type algorithms and graph-search techniques for
minimizing the cost of individual transpositions, and dynamic programing
algorithms for finding minimum cost cycle decompositions. The presented
algorithms have applications in information theory, bioinformatics, and
algebra.
