Approximation Algorithms for Facility Location Prob- lems in Graphs

dc.contributor.authorJena, Sangram Kishor
dc.date.accessioned2021-06-22T04:24:01Z
dc.date.accessioned2023-10-20T12:30:23Z
dc.date.available2021-06-22T04:24:01Z
dc.date.available2023-10-20T12:30:23Z
dc.date.issued2021
dc.descriptionSupervisor: Gautam Kumar Dasen_US
dc.description.abstractDominating set and its variants have been studied extensively in the literature and are of broad and current research interest to many researchers due to its wide range of applications, including, but not limited to, networks, VLSI, clustering, map labeling, coding theory, etc. In this thesis, minimum dominating set problem and some of its variants, such as maximum distance-d independent set, minimum distance- d dominating set, minimum d-distance m-tuple (`; r)-dominating set, minimum vertex-edge dominating set, and minimum total dominating set problems are studied. All the aforementioned problems are NP-hard and none of them admit constant factor approximation algorithms for general graphs, unless P = NP. This motivated us to study the problems for special graph classes. We are the rst to de ne the d-distance m-tuple (`; r)-dominating set problem in general graphs, which is a collection of problems depending on the values of d; m; `, and r and all the other four problems are studied in unit disk graphs (UDGs) with known disk position for designing simple constant factor approximation algorithms with low time complexity and polynomial-time approximation schemes that outperform the existing results in the literature. Firstly, we study the geometric maximum distance-d independent set (GMDdIS) problem, for an integer d 3. We show that the decision version of the GMDdIS problem (for d 3) is NP-complete in unit disk graphs. Next, we propose a simple 4-factor approximation algorithm for GMDdIS problem in d2nO(d) time. Finally, we propose a PTAS for this problem of size at least 1(1+ 1k )2 jOPTj in k2nO(k) time, where jOPTj is the maximum cardinality of a GMDdIS. Secondly, we study the geometric minimum distance-d dominating set (GMDdDS) problem in unit disk graphs. We show that the decision version of the GMDdDS problem (for d 2) is NP-complete in unit disk graphs. We propose a simple 4-factor approximation algorithm for GMDdDS problem in d2nO(d) time, and a PTAS for this problem of size at most (1+ 1k )2 jOPTj in k2nO(k) time, where OPT is the minimum cardinality of a GMDdDS. Next, we study the minimum d-distance m-tuple (`; r)-dominating set ((d; m; `; r) set) problem in general graphs. In this problem, we prove that the problem of deciding whether a graph G has a 1-distance m-tuple (`; r)-dominating set for each xed value of m; `, and r of cardinality at most k is NP-complete for gen- eral graphs. Next, we prove that the problem of deciding whether a graph G has a d-distance m-tuple (`; 2)-dominating set for each xed value of d(> 1);m, and ` of cardinality at most k is NP-complete. We also prove that for any " > 0, the 1-distance m-tuple (`; r)-domination problem and the d-distance m-tuple (`; 2)- domination problem cannot be approximated within a factor of ( 12 􀀀 ") ln jV j and ( 1/4 􀀀 ") ln jV j, respectively, unless P = NP. Next, we introduce a variant of dominating set problem in UDGs and we call this problem as the geometric minimum vertex-edge dominating set (GMVEDS) problem. Simply, a vertex pi 2 V , vertex-edge dominates every edge pipj , as well as every edge adjacent to these edges. We prove that the problem GMVEDS belongs to the NP-hard class in unit disk graphs. We propose a simple 4-factor approximation algorithm in polynomial time. We also designe a PTAS for this problem, which runs in O(nc) time, where c = O( 1 log 1 ). Finally, we study the geometric minimum total dominating set (GMTDS) problem in UDGs. In the GMTDS problem, we prove that the decision version of the TDS problem in the unit disk graph is NP-complete. Next, we propose a simple 8-factor approximation algorithm in O(n log k) time, where n is the input size and k is the output size of the algorithm. We also propose a PTAS for this problem of size at most (1 + 1k )2 jOPTj in O(k2n2(d2 p 2ke)2) time, where OPT is the optimum solution.en_US
dc.identifier.otherROLL NO.156123017
dc.identifier.urihttps://gyan.iitg.ac.in/handle/123456789/1862
dc.language.isoenen_US
dc.relation.ispartofseriesTH-2419;
dc.subjectMATHEMATICSen_US
dc.titleApproximation Algorithms for Facility Location Prob- lems in Graphsen_US
dc.typeThesisen_US
Files
Original bundle
Now showing 1 - 2 of 2
No Thumbnail Available
Name:
Abstract-TH-2419_156123017.pdf
Size:
147.75 KB
Format:
Adobe Portable Document Format
Description:
ABSTRACT
No Thumbnail Available
Name:
TH-2419_156123017.pdf
Size:
2.08 MB
Format:
Adobe Portable Document Format
Description:
THESIS
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.71 KB
Format:
Plain Text
Description: