PhD Candidate: Santanu Bhowmick
My dissertation examines certain fundamental geometric optimization problems that lie in the intersection of the areas of clustering and covering. Clustering is used for inferring useful patterns from data in fields as diverse as natural sciences, psychology, medicine, engineering, economics and marketing. Geometric covering problems arise in the context of sensor networks, in which the objective is uninterrupted monitoring of a region using sensors that have a fixed range and limited duration of continuous operation. Most versions of clustering and covering problems are NP-hard i.e. under widely believed assumptions, it is not possible to obtain an optimal solution for every instance of the problem efficiently.
An example of a covering problem that is considered in this dissertation is the metric multi cover (MMC) problem. 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 servers in Y, such that each client in X is covered by at least k disks centered at servers in Y, while minimizing sum of the radii of the disks. The MMC problem is motivated by fault-tolerant sensor network design that optimizes energy consumption. Prior works described algorithms that gave an O(k) approximation to the problem, i.e., the cost of the solution obtained increased linearly with k, making the solutions potentially impractical for higher values of the demand k.
Some other variants of the MMC problem that we consider include non-uniform coverage requirement of the clients, and restriction in the number of servers that can be used. We also examine simple geometric algorithms for regular covering that give a constant factor approximation, in order to facilitate deeper understanding of metric covering problems.
In this talk, I shall talk about two key contributions of my PhD thesis:
Advisor: Kasturi R. Varadarajan