A Partitioning Scheme for the Maximum Independent Set of Rectangles
A (2+ε)-Approximation Algorithm for Maximum Independent Set of Rectangles
We study the maximum independent set of rectangles (misr) problem, where we are given a set of axis-parallel rectangles in the plane and the goal is to select a subset of non-overlapping rectangles of maximum cardinality.In a recent breakthrough, mitchell [2021] obtained the first constant-factor approximation algorithm for misr and it achieves an approximation ratioof 10 and it is based on a dynamic program that intuitively recursively partition the input plane into special polygons called corner-clipped rectangles (ccrs) without intersecting certain special horizontal linesegments called fences.In this paper, we present an algorithm for misr which is also based on a recursive partitioning scheme.First, we use a partition into a class of axis-parallel polygons with constant complexity each that are more general than corner-clipped rectangles.
