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.