Sai Praneeth Reddy

September 14, 2015

# Maximum Independent Set of Rectangles

With Prof. Sandeep Sen, and Guntash Singh Arora.

We are given a set of unweighted axis-parallel rectangles and we are to choose the largest subset which do not intersect with each other. Say we are given a set of n rectangles R, and OPT(R) denotes the optimal independent set. We can alternatively construct an intersection graph of the set R where each node corresponds to a rectangle with edges between intersecting rectangles. Chalmersook and Chuzhoy 2009, in a breakthrough result, give an extremely invvolved O(\log\log n) approximation algorithm. There has however been no followup work on this result, probably because of the complexity of the techniques used. We show a simpler O(\log\log n) approximation algorithm i.e. we obtain a set S such that |S| log log n = W(|OPT(R)|). As a byproduct, we also give a algorithm which enjoys better approximation factor when the optimal set is large. The algorithm proceeds in two steps:
• We first sparsify the intersection graph. Given an input graph R with an maximum independent set OPT(R), we construct a subgraph R¢ of size close to OPT(R) and has an maximum independent set nearly the size of R
• Given that we have a graph in which the optimum is nearly the size of the graph, we use a simple local search to find the local optima \Lopt.
Here is a more detailed writeup of the algorithm. We conjecture that the above algorithm can also be generalized to weighted rectangles. I also gave a talk describing new developments.

Another line of work started by Anna Adamaszek, and Andreas Wiese (FOCS 2013) tackles the case of Maximum Weight Independent Set of Rectangles (MWISR) problem. They present a (1+epsilon)-approximation algorithm for the MWISR problem with quasi-polynomial running time 2^{poly(log n/epsilon)} using a separator based approach. Our survey of related work can be found Here.