# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 3 Inversions-Based Approximation Algorithms for Unsigned Permutations  
In this section, we present approximation algorithms based on the concept of inversions for the sorting unsigned \(\lambda\)-permutations problems we are addressing. The next lemma shows that it is always possible to remove at least one inversion from a \(\lambda\)-permutation by applying one \(\lambda\)-operation which results in a \(\lambda\)-permutation. **Lemma 3**. : _For any \(\lambda\)-permutation \(\pi\
eq\iota\), we can apply a 2-reversal or a 2-transposition to obtain a \(\lambda\)-permutation with \(\operatorname{Inv}(\pi)-1\) inversions._  
Proof. : Let \(\pi_{j}=i\) be the smallest element out-of-place in \(\pi\). Initially, note we have inversion \((\pi_{j-1},\pi_{j})\), since \(\pi_{j-1}>\pi_{j}\) and \(j-1<j\). Let \(\sigma\) be a 2-operation that swaps elements \(\pi_{j-1}\) and \(\pi_{j}\), and let \(\pi^{\prime}=\pi\cdot\sigma\). It is easy to see that \(\operatorname{Inv}(\pi^{\prime})=\operatorname{Inv}(\pi)-1\), since such inversion was removed, and note that there always exists a \(\lambda\)-reversal or a \(\lambda\)-transposition equivalent to \(\sigma\), because the elements are adjacent, and, so, both only swap two elements. Observe that, in \(\pi^{\prime}\), element \(\pi_{j}\) is closer to its correct position, since it was moved to the left. Hence, we follow by showing that \(\pi^{\prime}\) is a \(\lambda\)-permutation by considering two cases according to the values of \(\pi_{j-1}=\pi^{\prime}_{j}\). If \(\pi_{j-1}\geq j\), then \(\pi_{j-1}\) is also closer to its correct position, in \(\pi^{\prime}\). Otherwise, \(\pi_{j-1}<j\). Thus, element \(\pi_{j-1}\) will be, in \(\pi^{\prime}\), one position away from its correct position. Then, note that \(|j-\pi_{j}|+1=(j-i)+1\leq\lambda\) because \(\pi\) is a \(\lambda\)-permutation. In addition, observe that we have \(|j-\pi^{\prime}_{j}|=j-\pi^{\prime}_{j}\) because \(\pi^{\prime}_{j}=\pi_{j-1}<j\), and \(j-\pi^{\prime}_{j}<j-i\) because \(\pi^{\prime}_{j}>i\), and, so, \(j-i\leq\lambda-1\). Therefore, \(\pi^{\prime}\) is a \(\lambda\)-permutation, and the result follows. A generic greedy approximation algorithm for the three problems we are addressing in this section is presented in the next theorem. It receives an integer \(\lambda\geq 2\) and a \(\lambda\)-permutation \(\pi\
eq\iota\) as input. It is greedy because it always tries to decrease the largest amount of inversions in \(\pi\). Since an unsorted permutation always contains inversions, the algorithm will finally sort \(\pi\). **Theorem 2**. : _There exist \(O(\lambda^{2})\)-approximation algorithms for the problems of Sorting Unsigned \(\lambda\)-Permutations by \(\lambda\)-Reversals, by \(\lambda\)-Transpositions, and by \(\lambda\)-Reversals and \(\lambda\)-Transpositions._  
Proof. : Let \(\lambda\geq 2\) be an integer, and let \(\pi\
eq\iota\) be a \(\lambda\)-permutation. Consider an algorithm which chooses a \(\lambda\)-operation \(\sigma\), such that \(\pi\cdot\sigma\) is a \(\lambda\)-permutation and \(\operatorname{Inv}(\pi\cdot\sigma)\) is as small as possible, and then it applies such operation over \(\pi\). The algorithm repeats the same process over the resulting permutation until it reaches the identity permutation. In the worst case, we always have one \(\lambda\)-operation reducing the number of inversions by one unit, as shown in Lemma 3. Therefore, the number of operations of such greedy algorithm is, at most, \(\operatorname{Inv}(\pi)\), and the approximation factor follows immediately from Lemma 1. Note that the distance is \(O(n^{2})\) because any unsigned permutation can be sorted with \(O(n^{2})\)\(\lambda\)-reversals or \(\lambda\)-transpositions. For Sorting Unsigned Permutations by \(\lambda\)-Reversals, at each step the algorithm considers \(O(\lambda^{2})\) possible reversals that can be chosen.