@article{(Open Science Index):https://publications.waset.org/pdf/3557,
	  title     = {Block Sorting: A New Characterization and a New Heuristic},
	  author    = {Swapnoneel Roy and  Ashok Kumar Thakur and  Minhazur Rahman},
	  country	= {},
	  institution	= {},
	  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.},
	    journal   = {International Journal of Mathematical and Computational Sciences},
	  volume    = {2},
	  number    = {2},
	  year      = {2008},
	  pages     = {133 - 139},
	  ee        = {https://publications.waset.org/pdf/3557},
	  url   	= {https://publications.waset.org/vol/14},
	  bibsource = {https://publications.waset.org/},
	  issn  	= {eISSN: 1307-6892},
	  publisher = {World Academy of Science, Engineering and Technology},
	  index 	= {Open Science Index 14, 2008},
	}