Final Exam - Covering and Clustering with Outliers and Other Constraints

June 29, 2020 - 2:00pm to 3:00pm
This exam will be held remotely.

PhD Candidate: Tanmay Inamdar


         Consider the following hypothetical scenario. Suppose that a telecom provider is seeking to provide cellular network coverage to a certain geographical region. Having surveyed the region, it has shortlisted a set of potential locations that may be suitable for installing cellular towers. Each tower can provide coverage to the population lying inside a circular area of a certain radius. Furthermore, the company wants to ensure that at least 90% of the population in the region receives coverage, since providing coverage to everyone would be prohibitively expensive. How should the company find the minimum number of towers to be installed at a subset of potential locations to achieve this goal?

         This is an example of a class of optimization problems known as "Partial Covering", or "Clustering with Outliers". Such problems are generally NP-hard, i.e., it is widely believed that there is no efficient algorithm to find the best solution for these problems. Therefore, we often have to settle for an approximation algorithm — an efficient algorithm that finds a solution with some provable guarantee on its cost.

         Consider the following variants of the aforementioned scenario. Suppose the population in the region is divided into two different demographics, and the company wants to ensure that the desired fraction of each demographic receives coverage. Alternatively, consider the situation where each tower can provide service to a limited number of customers. We also design approximation algorithms for the variants of covering and clustering problems that formalize these additional considerations.

Advisor: Kasturi Varadarajan

Please contact Tanmay for further details, if you wish to join his final exam.