%0 Journal Article
	%A Swapnoneel Roy and  Ashok Kumar Thakur and  Minhazur Rahman
	%D 2008
	%J International Journal of Mathematical and Computational Sciences
	%B World Academy of Science, Engineering and Technology
	%I Open Science Index 14, 2008
	%T Block Sorting: A New Characterization and a New Heuristic
	%U https://publications.waset.org/pdf/3557
	%V 14
	%X 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.
	%P 133 - 139