Fair and Fast k-Center Clustering for Data Summarization

Abstract

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

1. is fast, both in theory and practice,
2. exhibits a worst-case constant-factor guarantee, and
3. gives promising computational results showing that there can be significant benefits in addressing both issues together instead of sequentially.