Approximate BLOCK SORTING

We consider the problem BLOCK-SORTING: Given a permutation, sort it by using a minimum number of block moves, where a block is a maximal substring of the permutation which is also a substring of the identity permutation, and a block move repositions the chosen block so that it merges with another block. Although this problem has recently been shown to be NP-hard [3], nothing better than a trivial 3-approximation was known. We present here the first non-trivial approximation algorithm to this problem. For this purpose, we introduce the following optimization problem: Given a set of increasing sequences of distinct elements, merge them into one increasing sequence with a minimum number of block moves. We show that the merging problem has a polyno-© World Scientific Publishing Company.