Approximation Algorithms for Socially Fair Clustering

Abstract

We present an (e^O(p) )-approximation algorithm for socially fair clustering with the _p-objective. In this problem, we are given a set of points in a metric space. Each point belongs to one (or several) of groups. The goal is to find a k-medians, k-means, or, more generally, _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 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()-approximation algorithms for the problem. The natural LP relaxation for the problem has an integrality gap of (). In order to obtain our result, we introduce a strengthened LP relaxation and show that it has an integrality gap of ( ) for a fixed p. Additionally, we present a bicriteria approximation algorithm, which generalizes the bicriteria approximation of Abbasi et al. [2021].

Tasks

Reproductions