Approximation Algorithm for Maximum Independent Set of Rectangles by Arindam Khan IISc, Bangalore

Maximum Independent Set of Rectangles (MISR) is a fundamental problem in computational geometry, approximation algorithms, and combinatorial optimization. In this problem, given a set of (possibly overlapping) rectangles on a plane one needs to find the maximum number of non-overlapping set of rectangles. MISR finds numerous applications in practice, e.g., in map labeling, data mining, and resource allocation. It also has rich connections with many important problems in graph theory and discrete geometry.

In a seminal result, Mitchell [3] presented a polynomial-time 10-approximation algorithm. In our recent paper [1], we give a $3$-approximation algorithm for MISR based on a recursive partitioning scheme. Subsequently, we have improved our approximation
ratio to $2+\varepsilon$ [2].

Even for the special case of independent set of axis-parallel line segments, the best-known approximation ratio is 2 and we believe that substantially new ideas are needed to obtain a better ratio than 2.

References:

[1] Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, Andreas Wiese: A 3-Approximation Algorithm for Maximum Independent Set of Rectangles. To appear in ACM-SIAM Symposium on Discrete Algorithms (SODA), 2022.

[2] Waldo Gálvez, Arindam Khan, Mathieu Mari, Tobias Mömke, Madhusudhan Reddy Pittu, Andreas Wiese: A (2+\epsilon)-Approximation Algorithm for Maximum Independent Set of Rectangles. CoRR abs/2106.00623 (2021)

[3] Joseph S. B. Mitchell: Approximating Maximum Independent Set for Rectangles in the Plane. To appear in IEEE Symposium on Foundations of Computer Science (FOCS), 2021.