Dissertation
Multi-covering problems and their variants
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Spring 2017
DOI: 10.17077/etd.qxqigvk3
Abstract
<p>In combinatorial optimization, covering problems are those problems where given a ground set and a family of subsets of the ground set, the objective is to find a minimum cost set of subsets whose union contains the ground set. We consider covering problems in the context of Computational Geometry, which is a subfield of Computer Science that deals with problems associated with geometric objects such as points, lines, disks, polygons etc. In particular, geometric covering is an active research area, where the ground set and the family of subsets are induced by geometric objects. Covering problems in combinatorial optimizations often have a geometric analogue that arises naturally, and though such problems remain NP-hard, it is often possible to exploit the geometric properties of the set system to obtain better approximation algorithms.</p>
<p>In this work, the fundamental problem that we consider is a generalization of geometric covering, where each element in the ground set may need to covered by more than one subset. To be precise, the problem is defined as follows: given two sets of points X, Y and a coverage function κ : X → Z+ ∪ {0}, construct balls centered on the points in Y such that each point in X is covered by at least κ(x) distinct balls. The objective in this problem is to minimize the total cost, which is a function of the radii of the balls. This problem is termed as the metric multi-cover (MMC) problem.</p>
<p>We first consider version of the MMC problem where κ(x) = 1 for all clients, i.e. the 1-covering case. The known results that give a constant factor approximation for this problem are variations of LP-based primal-dual algorithm. We use a modified local search technique, motivated by geometric idea, to derive a simple, constant- factor approximation for this problem in Chapter 2.</p>
<p>We then look at the MMC problem where the point sets X,Y are in the Euclidean plane, and each client x ∈ X needs to be covered by at least κ(x) distinct disks centered on the points in Y . In Chapter 4, we give the first polynomial time constant factor approximation for this problem, in which the constant is independent of the coverage function κ. Our solution also has an incremental property, which allows the algorithm to handle increases in the coverage requirement by increasing the radii of the current server disks, without affecting the approximation factor.</p>
<p>In the next problem, we move from the Euclidean plane to arbitrary metric spaces where we consider the uniform MMC problem. In this problem, each client x has the demand κ(x) = k, where k > 0 is an integer. We give the first constant factor approximation (independent of k) for this problem. The key contribution that led to this result is the formulation of a partitioning scheme of the servers in the uniform MMC problem, that reduces the uniform MMC problem to k instances of 1-covering problem, while preserving the optimality of the solution to a constant multiplicative factor. We present the partitioning scheme as an independent result in Chapter 5, which we then use to solve the uniform MMC problem in Chapter 6.</p>
<p>The MMC problem with arbitrary coverage function κ is then considered in Chapter 7. The key challenge that the non-uniform version presents is that the symmetry of the server partitioning scheme breaks down as the coverage demands of clients are independent of each other. We present a constant factor algorithm for this problem in Chapter 7.</p>
<p>The last problem that we consider is the t-MMC problem, which is a restricted version of the uniform MMC problem. The objective is to compute a cover in which each client is covered by at least k distinct server disks, using atmost t server disks in total. This problem is a generalization of the clustering problem (where k = 1), and to our knowledge this is the first time this generalization has been considered. We give a constant factor approximation for this problem in Chapter 8.</p>
Details
- Title: Subtitle
- Multi-covering problems and their variants
- Creators
- Santanu Bhowmick - University of Iowa
- Contributors
- Kasturi Varadarajan (Advisor)Sriram Pemmaraju (Committee Member)Sukumar Ghosh (Committee Member)Samuel Burer (Committee Member)Aaron Stump (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Computer Science
- Date degree season
- Spring 2017
- DOI
- 10.17077/etd.qxqigvk3
- Publisher
- University of Iowa
- Number of pages
- ix, 105 pages
- Copyright
- Copyright © 2017 Santanu Bhowmick
- Language
- English
- Date submitted
- 08/02/2017
- Description illustrations
- illustrations
- Description bibliographic
- Includes bibliographical references (pages 101-105).
- Public Abstract (ETD)
In this dissertation, we examine the metric multi-cover (MMC) problem and its variants. We are given two point sets X (clients) and Y (servers) in a metric space and a non-negative integer k. The goal is to find an assignment of radii to the servers, such that each client is covered by at least k disks centered at the servers, while minimizing the sum of the area of the disks. The MMC problem arises in the design of wireless sensor networks, where each sensor has a limited energy source. The energy consumed is considered to be linear in the area of the region covered by each sensor. Some applications may require multiple sensors monitoring an area for event detection, whereas in other applications, security or fault-tolerance requirements may mandate a multi-cover of the clients. Prior works described algorithms that gave an O(k) approximation to the problem, i.e., the cost of the solutions obtained increased linearly with k, making them impractical for high values of k.
In this work, we derive constant-factor approximations for the MMC problem, in which the constant factor guarantee is independent of the demand k. We extend the same approximation guarantee for some variants of the MMC problem, which include a version having non-uniform coverage requirement of the clients, and one in which there is a restriction in the number of servers that can be used. We also give a simple geometric constant-factor approximation for regular covering, in order to facilitate deeper understanding of metric covering problems.
- Academic Unit
- Computer Science
- Record Identifier
- 9983776904702771
Metrics
388 File views/ downloads
592 Record Views