Abstract: Classical k-clustering problems like k-median and k-means have long-standing relevance in computer science and allied fields. I will introduce a generalization of these problems, called aggregate k-clustering, where a common solution of some T input instances is evaluated via an aggregate cost function, e.g., the sum of the T clustering costs. These T instances differ only in the metric, i.e., the distance function among the input points. This represents a requirement that the entire point-set must be served in each instance. This problem is inspired by seasonal road closures, and the need to keep critical services like hospitals accessible to everyone in every season. From similar motivations, I will introduce a related problem: the edge-edit sensitivity of clustering on graph metrics, where we are interested in how insertions and/or deletions of edges in the input affect the output of a clustering algorithm. We will formalize this in a few different ways, and understand its applicability to aggregate clustering. I will outline results related to both problems, along with open questions that will inform my future research. This talk is based on joint work with Deeparnab Chakrabarty and Jonathan Conroy.

About the Speaker: Ankita is a sixth-year PhD student in the Department of Computer Science at Dartmouth College, USA. They are advised by Deeparnab Chakrabarty, and their doctoral work is on approximation algorithms for center-based k-clustering. Their broader interest is in algorithm design with a theoretical core, with some forays into empirical subfields. In addition to their theoretical clustering research, they have contributed to diverse areas such as data analysis, social choice, machine learning, and underwater robotics.