NONOVERLAPPING LOCAL ALIGNMENTS (WEIGHTED INDEPENDENT SETS OF AXIS-PARALLEL RECTANGLES)

We consider the following problem motivated by an application in compu tational molecular biology. We are given a set of weighted axis-parall el rectangles such that for any pair of rectangles and either axis, th e projection of one rectangle does not enclose that of the other. Defi ne a pair to be independent if their projections in both axes are disj oint. The problem is to find a maximum-weight independent subset of re ctangles. We show that the problem is NP-hard even in the uniform case when all the weights are the same. We analyze the performance of a na tural local-improvement heuristic for the general problem and prove a performance ratio of 3.25. We extend the heuristic to the problem of f inding a maximum-weight independent set in (d + 1)-claw-free graphs, a nd show a tight performance ratio of d - 1 + 1/d. A performance ratio of d/2 was known for the heuristic when applied to the uniform case. O ur contributions are proving the hardness of the problem and providing a tight analysis of the local-improvement algorithm for the general w eighted case.