# On Approximating Maximum Independent Set of Rectangles

arXiv: https://arxiv.org/abs/1608.00271 · HTML: https://mlsanity.com/paper/1608.00271/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2016.

## Built on by (most cited first, 2 of 2)

- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)

## Abstract (arXiv)

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-ε)-approximation algorithm with running time n^O(operatornamepoly(log n)/ε). 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 - ε)-approximation in time n^O(operatornamepoly(loglogn / ε)). We introduce several new technical ideas, that we hope will lead to further progress on this and related problems.