A 1.375-Approximation Algorithm for Sorting by Transpositions with Faster Running Time

Abstract

Sorting Permutations by Transpositions is a famous problem in the Computational Biology field. This problem is NP-Hard, and the best approximation algorithm, proposed by Elias and Hartman in 2006, has an approximation factor of 1.375. Since then, several researchers have proposed modifications to this algorithm to reduce the time complexity. More recently, researchers showed that the algorithm proposed by Elias and Hartman might need one more operation above the approximation ratio and presented a new 1.375-approximation algorithm using an algebraic approach that corrected this issue. This algorithm runs in $O(n^6)$ time. In this paper, we present an efficient way to fix Elias and Hartman algorithm that runs in $O(n^5)$. By comparing the three approximation algorithms with all permutations of size $n \le 12$, we also show that our algorithm finds the exact distance in more instances than the previous two algorithms.