Maximum Independent Set of Rectangles - An Empirical Study

Abstract

We study the Maximum Independent Set of Rectangles (MISR) problem. The problem involves a collection of n axis-parallel rectangles in 2D with weights. For the unweighted case, the goal is to find the maximum number of non-overlapping rectangles, while for the weighted case, the aim is to select the subset of non-overlapping rectangles with the maximum total weight. MISR is a special case of the classical Maximum Independent Set problem on graphs, where the input is limited to intersection graphs of axis-parallel rectangles in a plane. The problem has many practical applications, such as map labeling, data mining, and resource allocation, which has led to significant attention from various research communities. As the problem is known to be NP-hard, the main focus has been on the design of approximation algorithms.

The focus of this thesis is to conduct empirical evaluations on various algorithmic and combinatorial questions related to the MISR problem. The thesis investigates the following problems and presents empirical results:

1. The current state-of-the-art approximation algorithms for the MISR problem are as follows: Chalermsook et al. (2020) proposed an O(log log n)-factor approximation algorithm for the weighted case, while Galvez et al. (2021) proposed a 3-factor approximation algorithm for the unweighted case. However, both of these algorithms are theoretical but not practical.

We have implemented two practical algorithms, namely a natural greedy algorithm and simple linear programming (LP) based algorithm, for the MISR problem. We have conducted experimental studies on these algorithms, using random and special distributions of axis parallel rectangles in the plane. Based on our experiments, we observed that the LP-based approach obtained an independent set which is at most 1% away from the optimum, whereas the independent set generated by the greedy approach is at most 9% away from the optimum. If we consider only randomly generated axis parallel rectangles, the LP-based approach obtained an independent set which is at most 0.5% away from the optimum.

2. We have empirically evaluated three combinatorial conjectures in the intersection graph of axis parallel rectangles involving the chromatic number (χ), clique number (ω), independence number (α), and piercing number (τ ). These conjectures have been studied well and are considered challenging open problems in the area of combinatorial geometry.

We have implemented simple algorithms to compute the quantities χ, ω, α, and τ . We have conducted experimental studies to evaluate these conjectures, using random and special distributions of axis parallel rectangles in the plane. The first conjecture is: χ/ω = O(1). The best known upper bound for the ratio is O(log ω), given by Chalermsook et al. (2020). In our experimental study, we have found that the ratio χ/ω is at most 1.38. The second conjecture is: τ /α = O(1). The best known upper bound for the ratio is O((log log α)^2), given by Correa et al. (2014). In our experimental study, we have found that the ratio τ /α is at most 1.27. The third conjecture is: (ω · α)/n = Ω(1). The best known lower bound for the ratio is Ω(1/(log log α)^2). In our experimental study, we have found that the ratio (ω · α)/n is at least 2.71. Thus, our empirical study validates these conjectures for both random and special distributions of axis-parallel rectangles.