We present an (e^{O(p)} \log \ell{\log\log\ell})-approximation algorithm for socially fair clustering with the \ell_p-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of \ell groups. The goal is to find a k-medians, k-means, or, more generally, \ell_p-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of u \text{ in group j} d(u,C)^p. The socially fair clustering problem was independently proposed by Abbasi, Bhaskara, and Venkatasubramanian [2021] and Ghadiri, Samadi, and Vempala [2021]. Our algorithm improves and generalizes their O(\ell)-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of \Omega(\ell). In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of \Theta(\log \ell{\log\log\ell}) for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. [2021].
We present an (e^{O(p)} \log \ell{\log\log\ell})-approximation algorithm for socially fair clustering with the \ell_p-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of \ell groups. The goal is to find a k-medians, k-means, or, more generally, \ell_p-clustering that is simultaneously good for all of the groups. More precisely, we need to find a set of k centers C so as to minimize the maximum over all groups j of u \text{ in group j} d(u,C)^p. The socially fair clustering problem was independently proposed by Ghadiri, Samadi, and Vempala [2021] and Abbasi, Bhaskara, and Venkatasubramanian [2021]. Our algorithm improves and generalizes their O(\ell)-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of \Omega(\ell). In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of \Theta(\log \ell{\log\log\ell}) for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. [2021].
R
Abbasi, Bhaskara, and Venkatasubramanian
Ghadiri, Samadi, and Vempala
R
Ghadiri, Samadi, and Vempala
Abbasi, Bhaskara, and Venkatasubramanian