The 1.375 Approximation Algorithm for Sorting by Transpositions Can Run in O(n log n) Time
Sorting a permutation by transpositions (SPbT) is an important problem in bioinformtics. In this article, we improve the running time of the best known approximation algorithm for SPbT.
algorithms combinatorial optimization np-completeness strings permutation trees