The research in this thesis is focused on the problem of Block Sorting, which has applications in Computational Biology and in Optical Character Recognition (OCR). A block in a permutation is a maximal sequence of consecutive elements that are also consecutive in the identity permutation. BLOCK SORTING is the process of transforming an arbitrary permutation to the identity permutation through a sequence of block moves. Given an arbitrary permutation π and an integer m, the Block Sorting Problem, or the problem of deciding whether the transformation can be accomplished in at most m block moves has been shown to be NP-hard. After being known to be 3-approximable for over a decade, block sorting has been researched extensively and now there are several 2-approximation algorithms for its solution. This work introduces new structures on a permutation, which are called runs and ordered pairs, and are used to develop two new approximation algorithms. Both the new algorithms are 2-approximation algorithms, yielding the approximation ratio equal to the current best. This work also includes an analysis of both the new algorithms showing they are 2-approximation algorithms.
| Identifer | oai:union.ndltd.org:unf.edu/oai:digitalcommons.unf.edu:etd-1604 |
| Date | 01 January 2015 |
| Creators | Huang, Jici |
| Publisher | UNF Digital Commons |
| Source Sets | University of North Florida |
| Detected Language | English |
| Type | text |
| Format | application/pdf |
| Source | UNF Theses and Dissertations |
Page generated in 0.0015 seconds