Seminars

View all Seminars  |  Download ICal for this event

Maximum Independent Set of Rectangles - An Empirical Study

Series: M.Tech (Research) Thesis Defense

Speaker: Alok Kumar Komal, M.Tech (Research) student, Dept. of C.S.A

Date/Time: Dec 11 10:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Prof. Sathish Govindarajan

Abstract:
We study the Maximum Independent Set of Rectangles (MISR) problem. The problem involves a collection of n axis-parallel rectangles with weights. The objective is to select the subset of non-overlapping rectangles with the maximum total weight. The unweighted setting is a special case where the weight of each rectangle is 1. The problem has many practical applications, such as map labelling, data mining, and resource allocation.

The focus of our work 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 in the MISR problem: Chalermsook et al. (2020) proposed an O(log log n)- factor approximation algorithm for the problem. In the unweighted setting, Galvez et al. (2021) proposed a 3-factor approximation algorithm. However, both algorithms are theoretical but not practical.

We have implemented two practical algorithms, namely a linear programming (LP)-based algorithm and a greedy algorithm for the MISR problem. We have conducted experimental studies on these algorithms, using randomly generated and special distributions of axis-parallel rectangles. 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 10% away from the optimum.

2. We have empirically evaluated three 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 randomly generated and special distributions of axis-parallel rectangles. The first conjecture is: ?/? = O(1). The best known upper bound 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.

Microsoft teams link:


Link