Foundations for center-based clustering: Worst-case approximations and modern developments

In the first part of this chapter, we detail center-based clustering methods, namely methods based on finding a “best” set of center points and then assigning data points to their nearest center. In particular, we focus on k-means and k-median clustering which are two of the most widely used clustering objectives. We describe popular heuristics for these methods and theoretical guarantees associated with them.We also describe how to design worst case approximately optimal algorithms for these problems. In the second part of the chapter, we describe recent work on how to improve on these worst case algorithms even further by using insights from the nature of real world clustering problems and datasets. Finally, we also summarize theoretical work on clustering data generated from mixture models such as a mixture of Gaussians.