# Approximation Algorithms for Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations
## 7 Conclusions  
In this work, we introduced the problems of Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations, considering reversals and transpositions on signed and unsigned permutations.  
We presented an NP-hardness proof for the models containing unsigned reversals, transpositions, and the combination of (signed or unsigned) reversals and transpositions, when \(\lambda=cnt^{d}\) for positive constants \(c\) and \(0<d\leq 1\). We developed algorithms with approximation factors of \(O(\lambda^{2})\), \(O(\lambda)\), and \(O(1)\) for all problems studied. Besides that, experiments were also performed in order to see their performance on simulated data. Tables 1 and 2 summarize these results.  
For future work, we intend to develop approximation algorithms with better approximation factors for the problems of Sorting \(\lambda\)-Permutations by \(\lambda\)-Operations. Another direction of future work is to study the complexity for the model containing only signed reversals and other values of \(\lambda\).  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & \multicolumn{2}{c}{**Reversals**} & \multicolumn{2}{c}{**Reversals and Transpositions**} \\ \hline  & **Approx.** & **Time** & **Approx.** & **Time** \\ \hline Breakpoints-based & \(10+2\lambda\) & \(O(n(n+\lambda^{2}))\) & 12 & \(O(n(n+\lambda))\) \\ Inversions-based & \(\frac{\lambda(\lambda-1)}{2}+\lambda\) & \(O(n^{2}\lambda^{3}\sqrt{\log\lambda})\) & \(\frac{\lambda(\lambda-1)}{2}+\lambda\) & \(O(n^{2}\lambda^{4}\sqrt{\log\lambda})\) \\ \hline \hline \end{tabular}
\end{table}
Table 1: Summary of the approximation results for the problems considering signed permutations. The columns “Approx.” and “Time” refer to the theoretical approximation factor and the worst-case complexity time, respectively.  
\begin{table}
\begin{tabular}{l c c c c c} \hline \hline  & \multicolumn{2}{c}{**Reversals**} & \multicolumn{2}{c}{**Reversals and Transpositions**} \\ \hline  & **Approx.** & **Time** & **Approx.** & **Time** \\ \hline Breakpoints-based & \(10+2\lambda\) & \(O(n(n+\lambda^{2}))\) & 12 & \(O(n(n+\lambda))\) & 12 & \(O(n(n+\lambda))\) \\ Inversions-based & \(O(\lambda^{2})\) & \(O(n^{2}\lambda^{3}\sqrt{\log\lambda})\) & \(O(\lambda^{2})\) & \(O(n^{2}\lambda^{4}\sqrt{\log\lambda})\) & \(O(\lambda^{2})\) & \(O(n^{2}\lambda^{4}\sqrt{\log\lambda})\) \\ \hline \hline \end{tabular}
\end{table}
Table 2: Summary of the approximation results for the problems considering unsigned permutations. The columns “Approx.” and “Time” refer to the theoretical approximation factor and the worst-case complexity time, respectively.  
**Author Contributions:** Conceptualization, G.H.S.M., A.O.A., C.N.L. and Z.D.; Data curation, G.H.S.M.; Formal analysis, G.H.S.M., A.O.A. and C.N.L.; Funding acquisition, Z.D.; Investigation, G.H.S.M., A.O.A., C.N.L. and Z.D.; Writing--original draft, G.H.S.M. and A.O.A.; Writing--review & editing, A.O.A., C.N.L and Z.D. All authors have read and agreed to the published version of the manuscript.  
**Funding:** This work was supported by the Brazilian Federal Agency for the Support and Evaluation of Graduate Education, CAPES, the National Counsel of Technological and Scientific Development, CNPq (grants 400487/2016-0, 425340/2016-3, and 304380/2018-0), and the Sao Paulo Research Foundation, FAPESP (grants 2013/08293-7, 2015/11937-9, 2017/12646-3, 2017/16246-0, and 2017/16871-1).  
**Data Availability Statement:** All algorithms were implemented and they are available at [[https://github.com/compbiogroup/lambda-permutations](https://github.com/compbiogroup/lambda-permutations)]([https://github.com/compbiogroup/lambda-permutations](https://github.com/compbiogroup/lambda-permutations)), alongside the instances used in the experiments.(accessed on 29 April 2021).  
**Conflicts of Interest:** The authors declare no conflict of interest.