@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}, }