Hardness of approximation for non-overlapping local alignments

✍ Scribed by Hiroyuki Nagashima; Koichi Yamazaki

• Publisher: Elsevier Science
• Year: 2004
• Tongue: English
• Weight: 652 KB
• Volume: 137
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00344-5

✦ Synopsis

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 con ict if two projections of the rectangles on an axis intersect. The problem we consider in this paper is to ÿnd a maximum weighted subset S ⊆ S of rectangles such that any two rectangles in S are not in con ict. In this paper, we show that max{((2 k -1)=((k + 1)2 k -1))L k; 3 ; ((2 k -1)=((2k + 1)2 k -1))L k; 6 } is a lower bound of the worst-case relative error of the problem, where L k; 3 and L k; 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 3 8668 .