Covering and clustering with outliers and other constraints

Consider the following hypothetical scenario. Suppose that a telecom provider company 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 provide coverage to at least 90% of the population in the region, since providing coverage to everyone would be prohibitively expensive. How should the company find the minimum number of towers from the set 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’. This is a recurring theme in the problems we consider in this thesis. Such problems are known to be 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, i.e., an efficient algorithm that finds a solution with some provable guarantee on its cost.

Consider the following variant of the aforementioned telecom scenario. Suppose the population in the region is divided into two different demographics, and the company wants to provide coverage to at least 90% of the population belonging to of each of the two demographics. Alternatively, suppose that each tower can only provide coverage to a limited number of customers. Therefore, there should be enough towers to go around, in the interest of not overburdening any particular tower beyond its specified capacity. In this thesis, we consider covering and clustering problems suggested by these scenarios, and design approximation algorithms for them.