Home » Publication » 26540

Dettaglio pubblicazione

2021, OPERATIONS RESEARCH LETTERS, Pages 787-789 (volume: 49)

Algorithms for fair k-clustering with multiple protected attributes (01a Articolo in rivista)

Bohm M., Fazzone A., Leonardi S., Menghini C., Schwiegelshohn C.

We study fair center based clustering problems. In an influential paper, Chierichetti, Kumar, Lattanzi and Vassilvitskii (NIPS 2017) consider the problem of finding a good clustering, say of women and men, such that every cluster contains an equal number of women and men. They were able to obtain a constant factor approximation for this problem for most center based k-clustering objectives such as k-median, k-means, and k-center. Despite considerable interest in extending this problem for multiple protected attributes (e.g. women and men, with or without citizenship), so far constant factor approximations for these problems have remained elusive except in special cases. We settle this question in the affirmative by giving the first constant factor approximation for a wide range of center based k-clustering objectives.
Gruppo di ricerca: Algorithms and Data Science
keywords
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma