A new approximation algorithm for cut-and-paste sorting of unsigned circular permutations

A cut-and-paste operation can be a reversal, a transposition, or a transreversal on circular or linear permutations. There are several approximation algorithms for sorting signed permutations by combinations of these operations. For sorting unsigned permutations, we only know an algorithm with performance ratio 3 and its improved version with performance ratio 2.8386+δ2.8386+δ allowing reversals and transpositions. In this paper, we present a 2.25-approximation algorithm for sorting unsigned circular permutations by cut-and-paste operations. A structure called tie is proposed to represent the alternating path of length 5. We can classify the ties into 6 types and find ways to remove the breakpoints for each type of ties, so that every cut-and-paste operation can reduce at least 43 breakpoints averagely. Our algorithm can be used to sort unsigned linear permutations and achieve the performance ratio 2.25 if another operation named revrev is allowed.

► We present a 2.25-approximation algorithm for unsigned cut-and-paste sorting. ► The breakpoint graph is used to find moves for sorting a permutation. ► We focus on the paths of 3 black and 2 gray edges and call them ties. ► For each type of ties, we can find 3 moves to remove at least 4 breakpoints.