Can I read Sorting of Permutations by Cost-Constrained Transpositions on EtoBox?

Sorting of Permutations by Cost-Constrained Transpositions by Farnoud, Farzad; Milenkovic, Olgica is a scholarly article available to read on EtoBox.

What is Sorting of Permutations by Cost-Constrained Transpositions about?

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.

Author

Farnoud, Farzad; Milenkovic, Olgica

Published

2010

Language

EN