Hardness of approximation for non-overlapping local alignments Original Research Article

Let S be a set of weighted axis-parallel rectangles such that for each axis no projection of one rectangle properly contains that of another. Two rectangles are in conflict if two projections of the rectangles on an axis intersect. The problem we consider in this paper is to find a maximum weighted subset S′⊆S of rectangles such that any two rectangles in S′ are not in conflict. In this paper, we show that max{((2k−1)/((k+1)2k−1))Lk,3,((2k−1)/((2k+1)2k−1))Lk,6} is a lower bound of the worst-case relative error of the problem, where Lk,3 and Lk,6 are the lower bounds of the worst-case relative error of MAX kSAT-3 and MAX kSAT-6, respectively. From the current best lower bound of MAX 2SAT-3 due to Berman and Karpinski, it can be shown that it is NP-hard to approximate the problem to within relative error less than 38668.