Final exam: Multi-Covering Problems and Their Variants

W326 PBB

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:

  • A constant factor approximation using a variation of Local Search for the MMC problem where k = 1. This represents the first approximation algorithm for this problem that does not rely on linear programming relaxations.
  • A partitioning technique for decomposing multi-covering into several instances of 1-covering, such that solving the individual instances give a solution for the multi-covering problem within a constant factor of the optimal solution. This technique works even for variants of the multi-covering problem, such as the version with non-uniform demands and the version where the number of servers used are restricted.

Advisor: Kasturi R. Varadarajan