## Approximating Maximum Independent Set for Rectangles in the Plane

Given a set ${\cal R}=\{R_1,\ldots,R_n\}$ of $n$ axis-aligned rectangles in the plane, the {\em maximum independent set of rectangles} (MISR) problem seeks a maximum-cardinality subset, ${\cal R}^*\subseteq {\cal R}$, of rectangles that are {\em independent}, meaning that any two rectangles of ${\cal R}^*$ are interior-disjoint. The MISR, which is known to be NP-hard, has geometric structure that enables approximation algorithms with far better performance than is known (or even possible) for maximum independent set in a general graph.