A (1+e)-Approximation Algorithm for Sorting by Short Block-Moves

摘要

Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in the study of 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. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A (1+epsiv)-approximation algorithm for this problem is presented, where epsiv relies on the ratio of the number of elements to the number of inversions in the permutation. We propose a new structure in the permutation graph called umbrella, which is the basis of the new algorithm and valuable for further study.