Fair and Fast k-Center Clustering for Data Summarization

Haris Angelidakis · Adam Kurpisz · Leon Sering · Rico Zenklusen

Hall E #613

Keywords: [ SA: Privacy-preserving Statistics and Machine Learning ] [ SA: Fairness, Equity, Justice and Safety ] [ MISC: Scalable Algorithms ] [ T: Optimization ] [ MISC: Unsupervised and Semi-supervised Learning ] [ OPT: Discrete and Combinatorial Optimization ]


We consider two key issues faced by many clustering methods when used for data summarization, namely (a) an unfair representation of "demographic groups'' and (b) distorted summarizations, where data points in the summary represent subsets of the original data of vastly different sizes. Previous work made important steps towards handling separately each of these two issues in the context of the fundamental k-Center clustering objective through the study of fast algorithms for natural models that address them.We show that it is possible to effectively address both (a) and (b) simultaneously by presenting a clustering procedure that works for a canonical combined model and(i) is fast, both in theory and practice,(ii) exhibits a worst-case constant-factor guarantee, and (iii) gives promising computational results showing that there can be significant benefits in addressing both issues together instead of sequentially.

Chat is not available.