Poster
Fair and Fast k-Center Clustering for Data Summarization
Haris Angelidakis · Adam Kurpisz · Leon Sering · Rico Zenklusen
Hall E #613
Keywords: [ T: Optimization ] [ SA: Fairness, Equity, Justice and Safety ] [ MISC: Unsupervised and Semi-supervised Learning ] [ MISC: Scalable Algorithms ] [ SA: Privacy-preserving Statistics and Machine 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.