Clustering with fairness constraints

In this talk, we will look at two notions of fair clustering that arise when we take into account such demographic profiles. The first problem we consider - "socially fair clustering" - ensures fairness for clients. In this problem, a collection of sets (groups) over clients is used to model the demographic profiles of clients. The task is to find k centers that minimize the maximum group cost. I will present an efficient parameterized approximation scheme (EPAS) for this problem under metrics of bounded doubling dimension. The second problem known as "diversity-aware clustering" ensures fairness in center selection. Here we are given a collection of sets (groups) over facilities that model the demographic profiles of facilities. Furthermore, each group has a lower bound and upper bound requirement indicating the number of centers in the solution from the group. The task is to find k centers that simultaneously minimize the clustering cost and satisfy the group requirements. We will see a constant-factor parameterized approximation algorithm for this problem.

The talk is based on two joint works: one with Fateme Abbasi, Sandip Banerjee, Jaroslaw Byrka, Parinya Chalermsook, Kamyar Khodamoradi, Daniel Marx, Roohani Sharma, and Joachim Spoerhase, and the other with Suhas Thejaswi, Bruno Ordozgoiti, and Michal Osadnik.