Algorithms for fair \(k\)-clustering with multiple protected attributes. (English) Zbl 1525.68198
Summary: We study fair center based clustering problems. In an influential paper, F. Chierichetti et al. [“Fair clustering through fairlets”, Preprint, arXiv:1802.05733] 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.
MSC:
| 68W25 | Approximation algorithms |
| 62H30 | Classification and discrimination; cluster analysis (statistical aspects) |
| 90B80 | Discrete location and assignment |
| 90C27 | Combinatorial optimization |
References:
| [1] | Ahmadian, S.; Epasto, A.; Knittel, M.; Kumar, R.; Mahdian, M.; Moseley, B.; Pham, P.; Vassilvitskii, S.; Wang, Y., Fair hierarchical clustering, (Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; Lin, H., Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020. Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020 (Virtual) (2020)), 6-12 |
| [2] | Ahmadian, S.; Epasto, A.; Kumar, R.; Mahdian, M., Fair correlation clustering, (Chiappa, S.; Calandra, R., The 23rd International Conference on Artificial Intelligence and Statistics. The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, Palermo, Sicily, Italy, 26-28 August 2020 (Online). The 23rd International Conference on Artificial Intelligence and Statistics. The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, Palermo, Sicily, Italy, 26-28 August 2020 (Online), Proceedings of Machine Learning Research, PMLR, vol. 108 (2020)), 4195-4205 |
| [3] | Anagnostopoulos, A.; Becchetti, L.; Fazzone, A.; Menghini, C.; Schwiegelshohn, C., Spectral relaxations and fair densest subgraphs, (The 29th ACM International Conference on Information and Knowledge Management. The 29th ACM International Conference on Information and Knowledge Management, CIKM ’20, Virtual Event, Ireland, October 19-23, 2020 (2020)), 35-44 |
| [4] | Backurs, A.; Indyk, P.; Onak, K.; Schieber, B.; Vakilian, A.; Wagner, T., Scalable fair clustering, (Proceedings of the 36th International Conference on Machine Learning. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, 9-15 June 2019 (2019)), 405-413 |
| [5] | Bandyapadhyay, S.; Fomin, F. V.; Simonov, K., On coresets for fair clustering in metric and Euclidean spaces and their applications, (Bansal, N.; Merelli, E.; Worrell, J., 48th International Colloquium on Automata, Languages, and Programming. 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021. 48th International Colloquium on Automata, Languages, and Programming. 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, Glasgow, Scotland (Virtual Conference), July 12-16, 2021, LIPIcs, vol. 198 (2021), Schloss Dagstuhl - Leibniz-Zentrum für Informatik), 23:1-23:15 |
| [6] | Bera, S. K.; Chakrabarty, D.; Flores, N.; Negahbani, M., Fair algorithms for clustering, (Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019. Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, Vancouver, BC, Canada, 8-14 December 2019 (2019)), 4955-4966 |
| [7] | Bercea, I. O.; Groß, M.; Khuller, S.; Kumar, A.; Rösner, C.; Schmidt, D. R.; Schmidt, M., On the cost of essentially fair clusterings, (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, September 20-22, 2019 (2019), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, MA, USA), 18:1-18:22 · Zbl 07650085 |
| [8] | Chierichetti, F.; Kumar, R.; Lattanzi, S.; Vassilvitskii, S., Fair clustering through fairlets, (Proceedings of the 30th Annual Conference on Neural Information Processing Systems (NIPS) (2017)), 5036-5044 |
| [9] | Cohen-Addad, V.; Saulpic, D.; Schwiegelshohn, C., A new coreset framework for clustering, (53rd Annual ACM SIGACT Symposium on Theory of Computing. 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 (2021)), 169-182 · Zbl 07765162 |
| [10] | Kleindessner, M.; Samadi, S.; Awasthi, P.; Morgenstern, J., Guarantees for spectral clustering with fairness constraints, (Proceedings of the 36th International Conference on Machine Learning. Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, 9-15 June 2019 (2019)), 3458-3467 |
| [11] | Kuhn, H. W.; Yaw, B., The Hungarian method for the assignment problem, Nav. Res. Logist. Q., 83-97 (1955) · Zbl 0143.41905 |
| [12] | Rösner, C.; Schmidt, M., Privacy preserving clustering with constraints, (45th International Colloquium on Automata, Languages, and Programming. 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, Prague, Czech Republic, July 9-13, 2018 (2018)), 96:1-96:14 · Zbl 1499.90117 |
| [13] | Schmidt, M.; Schwiegelshohn, C.; Sohler, C., Fair coresets and streaming algorithms for fair k-means, (Approximation and Online Algorithms - 17th International Workshop. Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers (2019)), 232-251 · Zbl 1535.68487 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
