mlsanityData to 7 Oct 2026

Fair Representation Clustering with Several Protected Classes

arXiv 2202.01391 ↗First posted 3 Feb 2022cs.DS cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study the problem of fair k-median where each cluster is required to have a fair representation of individuals from different groups. In the fair representation k-median problem, we are given a set of points X in a metric space. Each point x∈ X belongs to one of ℓ groups. Further, we are given fair representation parameters αj and βj for each group j∈ [ℓ]. We say that a k-clustering C1, cdots, Ck fairly represents all groups if the number of points from group j in cluster Ci is between αj |Ci| and βj |Ci| for every j∈[ℓ] and i∈ [k]. The goal is to find a set C of k centers and an assignment φ: Xrightarrow C such that the clustering defined by (C, φ) fairly represents all groups and minimizes the ℓ1-objective sumx∈ X d(x, φ(x)). We present an O(log k)-approximation algorithm that runs in time nO(ℓ). Note that the known algorithms for the problem either (i) violate the fairness constraints by an additive term or (ii) run in time that is exponential in both k and ℓ. We also consider an important special case of the problem where αj = βj = fracfjf and fj, f ∈ mathbbN for all j∈ [ℓ]. For this special case, we present an O(log k)-approximation algorithm that runs in (kf)O(ℓ)log n + poly(n) time.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 24 of its 42 references that are in the map. First posted on arXiv 3 Feb 2022.

Builds on

24 of 42 references.

References · 24

  1. 2014Certifying and removing disparate impactcited by 715
  2. 2016Fair prediction with disparate impact: A study of bias in recidivism prediction instrumentscited by 671
  3. 2016Inherent Trade-Offs in the Fair Determination of Risk Scorescited by 582
  4. 2018Fair Clustering Through Fairletscited by 176
  5. 2019Fair Algorithms for Clusteringcited by 98
  6. 2019Scalable Fair Clusteringcited by 78
  7. 2019Proportionally Fair Clusteringcited by 69
  8. 2019Fair k-Center Clustering for Data Summarizationcited by 65
  9. 2020Individual Fairness for k-Clusteringcited by 56
  10. 2019Coresets for Clustering with Fairness Constraintscited by 51
  11. 2019Clustering without Over-Representationcited by 50
  12. 2018On the cost of essentially fair clusteringscited by 44
12 more
  1. 2020Fair clustering via equitable group representationscited by 43
  2. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  3. 2020Probabilistic Fair Clusteringcited by 28
  4. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  5. 2019A Center in Your Neighborhood: Fairness in Facility Locationcited by 26
  6. 2020A Pairwise Fair and Community-preserving Approach to k-Center Clusteringcited by 26
  7. 2021Approximation Algorithms for Socially Fair Clusteringcited by 25
  8. 2021Fair Clustering Under a Bounded Costcited by 21
  9. 2020A Notion of Individual Fairness for Clusteringcited by 20
  10. 2020On Coresets for Fair Clustering in Metric and Euclidean Spaces and Their Applicationscited by 19
  11. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  12. 2020Fair Clustering with Multiple Colorscited by 9

Built on by

Cited by year

Citing papers per year: 2023: 1; 2024: 3.

4 papers.

  1. 2023Approximation Algorithms for Fair Range Clusteringcited by 10
  2. 2024On Socially Fair Low-Rank Approximation and Column Subset Selectioncited by 2
  3. 2024Scalable Algorithms for Individual Preference Stable Clusteringcited by 1
  4. 2024A Polynomial-Time Approximation for Pairwise Fair k-Median Clusteringcited by 0