Abstract
Sorting permutations by short block moves is an interesting combinatorial problem derived from genome rearrangements. A short block move is an operation on a permutation that moves an element at most two positions away from its original position. The problem of sorting permutations by short block moves is to sort a permutation by the minimum number of short block moves. Our previous work showed that a special class of sub-permutations (named umbrella) can be optimally sorted in \(O(n^{2})\) time. In this paper, we devise an 5/4-approximation algorithm for sorting general permutations by short block moves, improving Heath’s approximation algorithm with a factor 4/3 and our previous work with an approximation factor 14/11. The key step of our algorithm is to decompose the permutation into a series of related umbrellas, then we can repeatedly exploit the polynomial algorithm for sorting umbrellas. To obtain the approximation factor of 5/4, we also present an implicit lower bound of the optimal solution, which improves Heath and Vergara’s result greatly.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bafna, V., Pevzner, P.: Sorting by transpositions. SIAM Journal on Discrete Mathematics 11(2), 224–240 (1998)
Bulteau, L., Fertin, G., Rusu, I.: Sorting by transpositions is difficult. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011, Part I. LNCS, vol. 6755, pp. 654–665. Springer, Heidelberg (2011)
Elias, I., Hartman, T.: A 1375-approximation algorithm for sorting by transpositions. IEEE/ACM Trans. Comput. Biology Bioinform 3(4), 369–379 (2006)
Eriksson, H., Eriksson, K., Karlander, J., Svensson, L., Wätlund, J.: Sorting a bridge hand. Discrete Mathematics 241(1–3), 289–300 (2001)
Hall, P.: On Representives of Subsets. J. London Math. Soc. 10, 26–30 (1935)
Heath, L.S., Vergara, J.P.C.: Sorting by bounded blockmoves. Discrete Applied Mathematics 88, 181–206 (1998)
Heath, L.S., Vergara, J.P.C.: Sorting by short block moves. Algorithmica 28(3), 323–354 (2000)
Jiang, H., Zhu, D., Zhu, B.: A (1+\(\varepsilon \))-approximation algorithm for sorting by short block-moves. Theoretical Computer Science 54(2), 279–292 (2011)
Jiang, H., Zhu, D.: A 14/11-approximation algorithm for sorting by short block-moves. Science China Information Sciences 54(2), 279–292 (2011)
Mahajan, M., Rama, R., Vijayakumar, S.: On sorting by 3-bounded transpositions. Discrete Mathematics 306(14), 1569–1585 (2006)
Sankoff, D., Leduc, G., Antoine, N., Paquin, B., Lang, B.F., Cedergren, R.: Gene order comparisons for phylogenetic inference: Evolution of the mitochondrial genome. Proc. Nat. Acad. Sci. USA 89, 6575–6579 (1992)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Jiang, H., Feng, H., Zhu, D. (2014). An 5/4-Approximation Algorithm for Sorting Permutations by Short Block Moves. In: Ahn, HK., Shin, CS. (eds) Algorithms and Computation. ISAAC 2014. Lecture Notes in Computer Science(), vol 8889. Springer, Cham. https://doi.org/10.1007/978-3-319-13075-0_39
Download citation
DOI: https://doi.org/10.1007/978-3-319-13075-0_39
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-13074-3
Online ISBN: 978-3-319-13075-0
eBook Packages: Computer ScienceComputer Science (R0)