Commenced in January 2007
Paper Count: 31100
Block Sorting: A New Characterization and a New Heuristic
Abstract:The Block Sorting problem is to sort a given permutation moving blocks. A block is defined as a substring of the given permutation, which is also a substring of the identity permutation. Block Sorting has been proved to be NP-Hard. Until now two different 2-Approximation algorithms have been presented for block sorting. These are the best known algorithms for Block Sorting till date. In this work we present a different characterization of Block Sorting in terms of a transposition cycle graph. Then we suggest a heuristic, which we show to exhibit a 2-approximation performance guarantee for most permutations.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330531Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1823
 M. Mahajan, R.Rama, V. Raman, and S. Vijaykumar. Approximate block sorting. International Journal of Foundation of Computer Science, to appear.
 M. Mahajan, R.Rama, and S. Vijaykumar. Towards constructing optimal block move sequences. In proc. of the 10th International Computing and Combinatorial conference, COCOON 2004, LNCS vol.3106, pages 33-42. Springer-Verlag, Aug 2004.
 P. Pevzner. Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge, MA, USA, 2000.
 V.Bafna and P.Pevzner. Genome rearrangements and sorting by reversals. SIAM Journal on Computing, 25:272-289, 1996.
 V.Bafna and P.Pevzner. Sorting by transpositions. SIAM Journal on Discrete Mathematics 11(2):224-240, may 1998.
 W.W. Bein, L.L. Larmore, L. Morales, and I.H. Sudborough. A Polymomial Time 2-Approximation for Block Sorting. Unpublished manuscript, available at http://www.egr.unlv.edu/ bein/pubs/twoblock.ps.
 W.W. Bein, L.L. Larmore, L. Morales, and I.H. Sudborough. Block sorting is hard. Intl. Jl. of Foundations of Computer science, 14:425-437, 2003.
 G.H Lin and G Xue. Signed genome arrangement by reversals and transpositions: Models and approximations. Theoretical Computer Science, 259:513-531, 2001.