On Approximating Maximum Independent Set of Rectangles

We study the Maximum Independent Set of Rectangles (MISR) problem: given a set of n axis-parallel rectangles, find a largest-cardinality subset of the rectangles, such that no two of them overlap. MISR is a basic geometric optimization problem with many applications, that has been studied extensively. Until recently, the best approximation algorithm for it achieved an O(log log n)-approximation factor. In a recent breakthrough, Adamaszek and Wiese provided a quasi-polynomial time approximation scheme: a (1-epsilon)-approximation algorithm with running time n(O(poly(log n)/epsilon)). Despite this result, obtaining a PTAS or even a polynomial-time constant-factor approximation remains a challenging open problem. In this paper we make progress towards this goal by providing an algorithm for MISR that achieves a (1 - epsilon)-approximation in time n(O(poly(log log n/epsilon))). We introduce several new technical ideas, that we hope will lead to further progress on this and related problems.