Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line: Algorithms and Complexity
MetadataShow full item record
Given a set of n axis-parallel rectangles in the plane, finding a maximum independent set (MIS), amaximumweighted independent set (WMIS), and aminimum hitting set (MHS), are basic problems in computational geometry and combinatorics. They have attracted significant attention since the sixties, when Wegner conjectured that the duality gap, equal to the ratio between the size of MIS and the size of MHS, is always bounded by a universal constant. An interesting case is when there exists a diagonal line that intersects each of the given rectangles. Indeed, Chepoi and Felsner recently gave a 6-approximation algorithm forMHSin this setting, and showed that the duality gap is between 3/2 and 6.We consider the same setting and improve upon these results. First, we derive an O(n2)-time algorithm for the WMIS when, in addition, every pair of intersecting rectangles have a common point below the diagonal. This improves and extends a classic result of Lubiw, and gives a 2-approximation algorithm for WMIS. Second, we show that MIS is NP-hard. Finally, we prove that the duality gap is between 2 and 4. The upper bound, which implies a 4-approximation algorithm for MHS, follows from simple combinatorial arguments, whereas the lower bound represents the best known lower bound on the duality gap, even in the general setting of the rectangles.
Artículo de publicación ISI
Núcleo Milenio Información y Coordinación en Redes ICM/FIC P10-024F; FONDECYT Grant 11110069 and FONDECYT Grant 11130266
DOI: DOI: 10.1007/s00454-014-9661-y
Quote ItemDiscrete Comput Geom (2015) 53:344–365
The following license files are associated with this item: