Maximum independent set of rectangles : (Record no. 431319)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 04192nam a22002177a 4500 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION | |
| fixed length control field | 240216b |||||||| |||| 00| 0 eng d |
| 082 ## - DEWEY DECIMAL CLASSIFICATION NUMBER | |
| Classification number | 516.028 |
| Item number | KOM |
| 100 ## - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Komal, Alok Kumar |
| 245 ## - TITLE STATEMENT | |
| Title | Maximum independent set of rectangles : |
| Remainder of title | an empirical study |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. (IMPRINT) | |
| Place of publication, distribution, etc | Bangalore: |
| Name of publisher, distributor, etc | Indian Institute of Science, |
| Date of publication, distribution, etc | 2023. |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | xiv, 56p.: |
| Other physical details | col. ill. |
| Accompanying material | e-Thesis |
| Size of unit | 2.237 MB |
| 500 ## - GENERAL NOTE | |
| General note | includes bibliographical references and index |
| 502 ## - DISSERTATION NOTE | |
| Dissertation note | MTech (Res); 2023; Computer Science and Automation |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc | 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. |
| 650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Computational Geometry |
| 650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Discrete Geometry |
| 650 ## - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name as entry element | Combinatorial Conjectures |
| 700 ## - ADDED ENTRY--PERSONAL NAME | |
| Personal name | advised by Govindarajan, Sathish |
| 856 ## - ELECTRONIC LOCATION AND ACCESS | |
| Uniform Resource Identifier | https://etd.iisc.ac.in/handle/2005/6335 |
| 942 ## - ADDED ENTRY ELEMENTS (KOHA) | |
| Koha item type | Thesis |
No items available.
