Approximation Algorithms for Facility Location Prob- lems in Graphs
No Thumbnail Available
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Dominating 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.
Description
Supervisor: Gautam Kumar Das
Keywords
MATHEMATICS