Algorithms for Facility Location Problems in Geometric Settings
No Thumbnail Available
Date
2023
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Facility Location Problems (FLPs) have been the subject of extensive research because of its diverse range of applications in VLSI, networks, clustering, and other areas. The covering problem and the dispersion problem are two popular FLPs. Covering problem refers to selecting a subset of covering objects from a given set of objects such that the union of the selected objects contains all the elements. On the other hand, the dispersion problem refers to selecting a subset of a given set of objects such that the closeness between the objects in the selected set is undesirable. In this thesis, we investigated capacitated version of the covering problem and the dispersion problem and many of its variants. We established a necessary and sufficient condition through which we can ensure whether the given instance of the capacitated covering problem is feasible or not. Further, we prove that the problem is NP-complete. Finally, we proposed a local search algorithm for the capacitated covering problem, and proved that the proposed algorithm is a PTAS. For the dispersion problem, we introduce the concept of dispersion partial sum, which generalizes the notion of dispersion. Based on the dispersion partial sum, we defined variants of the dispersion problem, namely the 1-dispersion problem, the 2-dispersion problem, and the c-dispersion problem. We studied the following dispersion problems in Euclidean space: the 2-dispersion problem in both R2 and R1, and the 1-dispersion problem in R1. We presented a (2√3 + ε)-factor approximation result for the 2-dispersion problem in R2. We also developed a common framework for the dispersion problem in Euclidean space, which produces a 2√3-factor approximation result and an optimal result for the 2-dispersion problem in R2 and R1, respectively. We studied the c-dispersion problem in a metric space. We proposed a greedy algorithm for the c-dispersion problem, which produces a 2c-factor approximation result. We also proved that the c-dispersion problem in a metric space parameterized by solution size is W[1]-hard. Finally, we considered a variant of the 1-dispersion problem, where a set of locations is the vertices of a convex polygon. This variant of the 1-dispersion problem is referred to as the convex 1-dispersion problem. We proposed an O(n3)-time algorithm that returns an optimal result where the objective is to select k(= 4) vertices for the convex 1-dispersion problem. We also proposed a √3 (≈ 1.733)-factor approximation algorithm for the convex 1-dispersion problem for any value of k.
Description
Supervisors: Rao, S V and Das, Gautam Kumar
Keywords
Facility Location Problem, Approximation Algorithms, Covering Problem, Dispersion Problem, NP-hard, W[1]-hard