Block Sorting: A New Characterization and a New Heuristic

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.

Authors:

• Swapnoneel Roy
• Ashok Kumar Thakur
• Minhazur Rahman

Keywords:

• Block Sorting
• Optical Character Recognition
• Genome Rearrangements
• Sorting Primitives
• ApproximationAlgorithms

References:

[1] M. Mahajan, R.Rama, V. Raman, and S. Vijaykumar.
Approximate block sorting. International Journal of
Foundation of Computer Science, to appear.
[2] 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.
[3] P. Pevzner. Computational Molecular Biology: An
Algorithmic Approach. MIT Press, Cambridge, MA,
USA, 2000.
[4] V.Bafna and P.Pevzner. Genome rearrangements and sorting
by reversals. SIAM Journal on Computing, 25:272-289, 1996.
[5] V.Bafna and P.Pevzner. Sorting by transpositions. SIAM
Journal on Discrete Mathematics 11(2):224-240, may 1998.
[6] 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.
[7] 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.
[8] G.H Lin and G Xue. Signed genome arrangement by reversals
and transpositions: Models and approximations. Theoretical
Computer Science, 259:513-531, 2001.