Block sorting is APX-hard

Block Sorting is an NP-hard combinatorial optimization problem motivated by applications in Computational Biology and Optical Character Recognition (OCR). It has been approximated in P time within a factor of 2 using two different techniques and the complexity of better approximations has been open for close to a decade now. In this work we prove that Block Sorting does not admit a PTAS unless P = NP i.e. it is APX-Hard. The hardness result is based on new properties, that we identify, of the existing NP-hardness reduction from E3-SAT to Block Sorting. In an saattempt to obtain an improved approximation for Block Sorting, we consider a generalization of the well-studied Block Merging, called k-Block Merging which is defined for each k ≥ 1, and the 1- Block Merging problem is the same as the Block Merging problem. We show that the optimum k-Block Merging is an 1 + 1/k -approximation to the optimum block sorting. We then show that for each k ≥ 2, we prove k-Block Merging to be NP-Hard, thus proving a dichotomy result associated with block sorting.