# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 5 Breakpoints-Based Approximation Algorithms  
In this section, we present approximation algorithms based on the concept of breakpoints for the five problems we are addressing. In the next lemma, we suppose that the smallest element out-of-place is in an increasing strip of a \(\lambda\)-permutation \(\pi\
eq\iota\). We show how to reduce the number of breakpoints of \(\pi\) by moving this strip to its correct position using an operation that may not be a \(\lambda\) -operation, but assuring that the resulting permutation is also a \(\lambda\)-permutation. Let \(\pi\) be a \(\lambda\)-permutation. Let \(|\pi_{j}|=i\) be the smallest element out-of-place in \(\pi\). Suppose that \(\pi_{j}\) is in an increasing strip \(S=(\pi_{j}\,\ldots\,\pi_{k})\). Then, \(\pi\cdot\tau(i,j,k+1)\) is a \(\lambda\)-permutation, \(b(\pi\cdot\tau(i,j,k+1))\leq b(\pi)-1\), and \((k+1-i)\leq 2(\lambda-1)\). Proof. : Let \(R=(\pi_{i}\,\ldots\,\pi_{j-1})\) be the segment of elements in \(\pi\) that will be transposed with \(S\). Observe that the absolute value of any element in \(R\) is greater than any element in \(S\), so \(\pi\cdot\tau(i,j,k+1)\) is a \(\lambda\)-permutation, since greater elements (in their absolute values) are moved to the right and smaller elements to the left. In addition, observe that, in \(\pi\), we have the three breakpoints \((\pi_{i-1},\pi_{i})\), \((\pi_{i},\pi_{j+1})\), and \((\pi_{k-1},\pi_{k})\), where the first one is because \(\pi_{i-1}=\pi_{j}-1=i-1\) and \(|\pi_{i}|>i=\pi_{j}\), and the second and third ones are because the strip's start and strip's end are at positions \(j\) and \(k\), respectively. Transposition \(\tau(i,j,k+1)\) moves the elements of \(S\) to their correct positions by transposing them with elements of \(R\), thus removing at least breakpoint \((\pi_{i-1},\pi_{i})\). Since a transposition can add, at most, three breakpoints, but we already had all of them and we removed at least \((\pi_{i-1},\pi_{i})\), we have \(b(\pi\cdot\tau(i,j,k+1))\leq b(\pi)-1\). By Lemma 2, we have \(|S|\leq\lambda-1\); thus, \(k+1-j\leq\lambda-1\). Since \(\pi\) is a \(\lambda\)-permutation, we have \(||\pi_{j}|-j|\leq\lambda-1\), and, by construction, \(\pi_{j}=i\); thus, \(|i-j|+1=j-i+1\leq\lambda-1\). Therefore, \(k+1-i\leq 2(\lambda-1)\). For a \(\lambda\)-permutation \(\pi\) with only increasing strips, the next lemma shows that it is possible to find a sequence with, at most, \(4\) transpositions that decreases the number of breakpoints in \(\pi\), assuring that all permutations generated in the process are \(\lambda\)-permutations. Using these operations, we can create an algorithm that sorts \(\pi\) using, at most, \(4b(\pi)\)\(\lambda\)-transpositions. Let \(\pi\) be a \(\lambda\)-permutation. Let \(|\pi_{j}|=i\) be the smallest element out-of-place in \(\pi\). Suppose that \(\pi_{j}\) is in an increasing strip \(S=(\pi_{j}\,\ldots\,\pi_{k})\). It is always possible to obtain a \(\lambda\)-permutation \(\pi\cdot\tau(i,j,k+1)\) with, at most, \(b(\pi)-1\) breakpoints by applying, at most, \(4\)\(\lambda\)-transpositions such that all intermediary permutations are \(\lambda\)-permutations. Proof. : Let \(R=(\pi_{i}\,\ldots\,\pi_{j-1})\) be the segment that will be moved to the right in \(\tau(i,j,k+1)\). Note that \(|S|\leq\lambda-1\), by Lemma 2, and \(|R|\leq\lambda-1\), because \(\pi\) is a \(\lambda\)-permutation. The idea is to apply a sequence with, at most, four \(\lambda\)-transpositions that divide both segments \(R=(\pi_{i}\,\ldots\,\pi_{j-1})\) and \(S=(\pi_{j}\,\ldots\,\pi_{k})\) into, at most, two parts each, where each part has, at most, \(\lfloor\lambda/2\rfloor\) elements, and then exchange each part of \(S\), at most, twice (and at least once), with the (possible) two parts of \(R\). If we had exactly \(\lambda-1\) elements in each of \(S\) and \(R\), such sequence would be \(\tau(i+\lfloor\lambda/2\rfloor,j,j+\lfloor\lambda/2\rfloor),\tau(i,i+\lfloor \lambda/2\rfloor,j),\tau(j,j+\lfloor\lambda/2\rfloor,k+1),\tau(i+\lfloor\lambda /2\rfloor,j,j+\lfloor\lambda/2\rfloor)\).