An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves

Abstract

Sorting permutations by short block moves is an interesting combinatorial problem derived from genome rearrangements. A short block move is an operation on a permutation that moves an element at most two positions away from its original position. The problem of sorting permutations by short block moves is to sort a permutation by the minimum number of short block moves. Our previous work showed that a special class of sub-permutations (named umbrella) can be optimally sorted in $O(n^{2})$ time. In this paper, we devise an 5/4-approximation algorithm for sorting general permutations by short block moves, improving Heath’s approximation algorithm with a factor 4/3 and our previous work with an approximation factor 14/11. The key step of our algorithm is to decompose the permutation into a series of related umbrellas, then we can repeatedly exploit the polynomial algorithm for sorting umbrellas. To obtain the approximation factor of 5/4, we also present an implicit lower bound of the optimal solution, which improves Heath and Vergara’s result greatly.