On Approximability of Block Sorting

Details On Approximability of Block Sorting On Approximability of Block Sorting

2011-10-05

arxiv.org/abs/1110.0892v1

Computer Science

Computational Complexity

Scientific paper

Block Sorting is a well studied problem, motivated by its applications in Optical Character Recognition (OCR), and Computational Biology. Block Sorting has been shown to be NP-Hard, and two separate polynomial time 2-approximation algorithms have been designed for the problem. But questions like whether a better approximation algorithm can be designed, and whether the problem is APX-Hard have been open for quite a while now. In this work we answer the latter question by proving Block Sorting to be Max-SNP-Hard (APX-Hard). The APX-Hardness result is based on a linear reduction of Max-3SAT to Block Sorting. We also provide a new lower bound for the problem via a new parametrized problem k-Block Merging.

Affiliated with

Also associated with

No associations

Rating

On Approximability of Block Sorting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Approximability of Block Sorting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Approximability of Block Sorting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-324622