Given a collection of data points, how can we partition them into clusters, so that the points in the same (resp. different) clusters are similar (resp. dissimilar) to one another, so as to reveal unknown structure in the data? This is a fundamental unsupervised learning task, with wide ranging applications in social network analysis, image segmentation, spam detection and medical imaging, among many others. The primary focus of this Dagstuhl Seminar is on the theoretical study of clustering algorithms, and specifically, on the design and analysis of approximation algorithms for metric clustering, where data points come from a metric space and their (dis)similarity is meansured by a distance function.

The study of clustering problems dates back several decades, and has led to the adaptation of versatile and powerful algorithm design techniques. In recent years, there has been a surge of activities in the study of clustering problems from different computational vantage points, leading to various new techniques for the development of approximation algorithms. These include new algorithm prototypes that are applicable to sublinear models, and geometric tools to deal with the challenges of high dimensionality. Each of these strands of research focuses on some challenge faced in modern applications involving massive and rapidly evolving data sets, and attempts to design clustering algorithms that overcome this challenge. This had led to a series of recent results on dynamic, online, streaming and massively parallel clustering, as well as on designing clustering algorithms whose outputs are fair, robust, and differentially private.

The seminar aims to bring together researchers working on clustering problems from these divergent perspectives. The topics to be the discussed at the seminar are:

• What are the major open questions? This research area has seen an explosive growth in recent years. In plenary talks and open problem sessions, we plan to survey state-of-the-art results and to identify key open questions.
• Can we find transferable algorithm design techniques? Clustering problems have been considered in a variety of computational models, such as dynamic, online, streaming, MPC, to name a few. A major focus of the seminar will be to identify common algorithm design principles that are transferable across these computational models.
• What strategies can bridge the gap between theory and practice of clustering algorithms? Clustering is a topic that has a diverse set of applications in unsupervised learning. An important goal we want to support is the development of clustering algorithms that are simultaneously: (i) practical and (ii) have strong theoretical guarantees. To this end, we plan to invite several industrial participants (and one of the organizers of this workshop works in industry).

Creative Commons BY 4.0

Sayan Bhattacharya, Shaofeng Jiang, Silvio Lattanzi, and Melanie Schmidt