Final exam - Digging Deeper into Clustering and Covering Problems

December 10, 2018 - 1:00pm
UCC 2520B

PhD Candidate: Sayan Bandyapadhyay


Consider the following two fictitious scenarios. (i) Suppose an organization wants to start a web news portal that will list all the online news articles of the day classified by their categories. However, the articles are assumed to have no category information, and thus here we want to guess the categories of the articles. (ii) Suppose a company has obtained the tender for placing mobile towers in a new city. In the initial plan, it has identified a large set of placement locations such that the towers can serve all the clients in the city. We want to select a "small'' number of towers from the plan that still can serve all the clients in the city. We note that the two above mentioned problems belong to the class of clustering problems and the class of covering problems, respectively. Clustering is the task of grouping a set of items into similar groups (or clusters) with respect to a similarity measure. Ideally, items in different groups should have low similarity. Often the items are represented by points in a high dimensional space. The distance between two items represents their similarity. On the other hand, covering is the task of selecting a subset of objects from a larger set, such that the objects in the subset "cover'' (or contain) a given set of elements. Ideally, one wants to find such a subset of the minimum size. Usually, the objects and the elements are modeled using geometric shapes and points, respectively. We have considered several clustering and covering problems in this thesis, and have designed improved algorithms for solving them. Our main contribution is to prove theoretical guarantees on the quality of the solutions produced by our algorithms.


Advisor: Kasturi Varadarajan