# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 5 Breakpoints-Based Approximation Algorithms
Let \(R=(\pi_{i}\,\dots\,\pi_{j-1})\) be the segment of elements that should be moved in order to put \(S\) in its correct position. Observe that the absolute value of any element in \(R\) is greater than any element in \(S\). The first operation, a \(\lambda\)-transposition, transposes \(S\) only with greater elements (in their absolute values); thus, the result is a \(\lambda\)-permutation. The second operation, a \(\lambda\)-reversal, just reverses a decreasing strip to put the elements of \(S\) in their correct positions; thus, it also results in a \(\lambda\)-permutation. Hence, we have as result a \(\lambda\)-permutation with at least one less breakpoint. The next theorems describe approximation algorithms for the problems we are addressing. Lemma 10 is auxiliary to Theorem 4. The algorithms receive an integer \(\lambda\geq 2\) and a \(\lambda\)-permutation \(\pi\
eq\iota\) as input. The goal is to decrease at least one unit on the number of breakpoints in \(\pi\) by moving elements to their correct positions (applying Lemmas 7 and 9). Since the only permutation with no breakpoints is the identity, they will, eventually, sort \(\pi\). **Lemma 10**. : _Let \(\pi\) be a \(\lambda\)-permutation. Let \(S=(j\dots i)\) be a decreasing strip in \(\pi\) (thus, \(i<j\)). Let \(\pi^{\prime}=\pi\cdot\rho(\pi_{|j|}^{-1},\pi_{|i|}^{-1})\) be the resulting permutation after reversing \(S\) in \(\pi\). Then, \(\pi^{\prime}\) is a \(\lambda\)-permutation._  
Proof. : First, note that element \(\pi_{j}\) is to the right of element \(\pi_{i}\). We show that the lemma follows by considering four cases, according to the positions of elements \(i\) and \(j\) in relation with the elements \(\pi_{|i|}\) and \(\pi_{|j|}\). Case (i), \(|i|<|j|<\pi_{|j|}^{-1}<\pi_{|i|}^{-1}\): note that both \(\pi_{|i|}\) and \(\pi_{|j|}\) are to the left of \(S\). Then, after reversing \(S\), element \(i\) is closer to its correct position, while element \(j\) is moved away from its correct position. Despite this, the distance between \(\pi_{|j|}\) and \(j\) in \(\pi^{\prime}\) is smaller than the distance between \(\pi_{|i|}\) and \(i\) in \(\pi\), and, so, if \(\pi\) is a \(\lambda\)-permutation, \(\pi^{\prime}\) is also a \(\lambda\)-permutation. Case (ii), \(|i|<\pi_{|j|}^{-1}\leq|j|<\pi_{|i|}^{-1}\): note that \(\pi_{|i|}\) is to the left of \(S\), and \(\pi_{|j|}\) is in \(S\). Then, after reversing \(S\), the element \(i\) is closer to its correct position and the distance of \(j\) to its correct position will still be less than \(\lambda\), since the size of \(S\) is, at most, \(\lambda\), as Lemma 2 shows. Case (iii), \(\pi_{|j|}^{-1}\leq|i|<\pi_{|i|}^{-1}\leq|j|\): similar to (ii). Case (iv), \(\pi_{|j|}^{-1}<\pi_{|i|}^{-1}\leq|i|<|j|\): similar to (i). **Theorem 4**. : _The problems of Sorting (Unsigned or Signed) \(\lambda\)-Permutations by \(\lambda\)-Reversals have \((10+2\lambda)\)-approximation algorithms._Proof. : Let \(\lambda\geq 2\) be an integer and \(\pi\
eq\iota\) be a \(\lambda\)-permutation. Consider an algorithm which first applies one \(\lambda\)-reversal over each decreasing strip of \(\pi\) in order to get a \(\lambda\)-permutation with only increasing strips. By Lemma 10, we guarantee that all intermediary permutations generated by these \(\lambda\)-reversals are \(\lambda\)-permutations. Then, the algorithm will repeatedly take the smallest element out-of-place and move the increasing strip that contains it to its correct position, obtaining a \(\lambda\)-permutation with at least one less breakpoint, until it reaches the identity permutation. As shown in Lemma 8, at most \(5+\lambda-1\)\(\lambda\)-reversals are needed to move each strip to its correct position. Since, maybe, one extra \(\lambda\)-reversal could have been applied in the beginning of the algorithm to transform such strip into an increasing one, we have that, at most, \(6+\lambda-1\)\(\lambda\)-reversals can be applied to remove at least one breakpoint.