## DIMACS TR: 95-36

## Nonoverlapping Local Alignments, Weighted Independent Sets of Axis
Parallel Rectangles

### Authors: Vineet Bafna, Babu Narayanan, R. Ravi

**
ABSTRACT
**

We consider the following problem motivated by an application in computational
molecular biology. We are given a set of weighted axis-parallel rectangles
such that for any pair of rectangles and either axis, the projection of one
rectangle does not enclose that of the other. Define a pair to be independent
if their projections in both axes are disjoint. The problem is to find a
maximum-weight independent subset of rectangles.
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 natural local-
improvement heuristic for the general problem and prove a performance
ration of 3.25. We extend the heuristic to the problem of finding a
maximum-weight independent set in (d+1)-claw free graphs, and show a tight
performance ration of (d - 1 + (1/d)). A performance ratio of d/2 was known
for the heuristic when applied to the uniform case. Our contributions are
proving the hardness of the problem and providing a tight analysis of the
local-improvement algorithm for the general weighted case.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-36.ps.gz

DIMACS Home Page