Abstract
In this talk, we study the following problem: given a collection of axis-parallel rectangles in the plane, our goal is to select a pairwise non-overlapping sub-collection whose cardinality is maximized. This problem has many applications including, e.g., map labeling, data mining, network routing, and resource management in network. The problem is NP-hard, and there were many O(log n) approximation algorithms for it. In this talk, we show an O(log log n) approximation algorithm. Our algorithm makes use of the connection between this problem and another half-century old problem on rectangle coloring, which could be of independent interest.