Algorithms for Generalized Clustering: Min-Max Objective to Cascaded Norms

Abstract: In this talk, I will consider the k-clustering problem with min-max objective: Given an input set of points P partitioned into L predefined groups, the aim is to find a k-clustering that minimizes the maximum average clustering cost (e.g., k-means cost) across these groups, reflecting fairness in applications like polling station or vaccination sites placement. I present a O(log L/ log log L)-approximation for the clustering problem with min-max objective, which exponentially improves over the previously known O(L)-approximation and is optimal up to a constant factor.

Moreover, I will discuss the generalization of the problem to (p,q)-cascaded norms and arbitrary weight functions over the points. As an application, this allows a “relaxed” way of enforcing the fairness requirement, as its objective interpolates between the objective of classic k-clustering and that of socially fair clustering. Moreover, the problem is closely related to other well-known problems in combinatorial optimization such as densest k-subgraph and min-k union.

Bio: Ali Vakilian is a Research Assistant Professor at TTIC. His research interests include algorithms for massive data, learning-augmented algorithms, and algorithmic fairness. Ali received his Ph.D. from MIT, where he was advised by Erik Demaine and Piotr Indyk. He completed his MS studies at UIUC where he was a recipient of the Siebel Scholar award.