Algorithms for clustering problems
Rajeev Motwani, Moses Charikar · 2001
Clustering problems arise in various contexts. Roughly speaking, clustering refers to partitioning a set of objects into groups of similar objects. The objects (e.g. documents or images) are usually represented as points in some space with a distance measure and the objective is to obtain clusters of points that are close to each other. Problems of this flavor also occur in discrete location theory, where the goal is to locate a set of facilities (e.g. factories or warehouses) so as to serve a given set of clients. In this thesis, we consider several algorithmic aspects of clustering problems, viewed as optimization questions. The quality of a clustering is typically measured by an objective function and the goal of an algorithm is to minimize this. For most natural objective functions, the corresponding optimization problem turns out to be NP-hard. In the face of this fundamental intractability, researchers have shifted their focus from exact solutions to obtaining approximate solutions that are guaranteed to be close to the optimal. The first part of the thesis focuses on the approximability of several natural clustering objectives. We describe approximation algorithms for classical clustering and location problems such as k-median and facility location. We use both linear programming based approaches as well as purely combinatorial approaches such as local search to achieve the currently best known approximation factors for these problems. Further, the ideas behind these algorithms extend to other problems such as minsum clustering. The second part of the thesis examines other algorithmic issues that arise in clustering. We study clustering problems in the presence of outliers which must be identified and excluded prior to clustering. We also formulate problems and describe results related to the incremental maintenance of clusters in a dynamic point set. Such problems arise when the data set is frequently updated and re-clustering is prohibitively expensive. Finally, we look at algorithmic techniques to deal with clustering large data sets, motivated by a real life application—that of clustering near duplicate documents in the AltaVista index.