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.
Algorithms for fair k-clustering with multiple protected attributes / Bohm, M.; Fazzone, A.; Leonardi, S.; Menghini, C.; Schwiegelshohn, C.. - In: OPERATIONS RESEARCH LETTERS. - ISSN 0167-6377. - 49:5(2021), pp. 787-789. [10.1016/j.orl.2021.08.011]
Algorithms for fair k-clustering with multiple protected attributes
Bohm M.;Fazzone A.;Leonardi S.;Menghini C.;Schwiegelshohn C.
2021
Abstract
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.File | Dimensione | Formato | |
---|---|---|---|
Bohm_Algorithms_2021.pdf
solo gestori archivio
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Tutti i diritti riservati (All rights reserved)
Dimensione
228.27 kB
Formato
Adobe PDF
|
228.27 kB | Adobe PDF | Contatta l'autore |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.