Loading...
Please wait, while we are loading the content...
Similar Documents
Hardness of approximation for non-overlapping local alignments
| Content Provider | Semantic Scholar |
|---|---|
| Author | Nagashima, Hiroyuki Yamazaki, Koichi |
| Copyright Year | 2004 |
| Abstract | 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 3/8668. |
| Starting Page | 293 |
| Ending Page | 309 |
| Page Count | 17 |
| File Format | PDF HTM / HTML |
| DOI | 10.1016/S0166-218X(03)00344-5 |
| Alternate Webpage(s) | https://www.researchgate.net/profile/Koichi_Yamazaki/publication/257000478_Hardness_of_approximation_for_non-overlapping_local_alignments/links/0046352a86a43a9a2f000000.pdf |
| Alternate Webpage(s) | https://doi.org/10.1016/S0166-218X%2803%2900344-5 |
| Volume Number | 137 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
