Fair Representation Clustering with Several Protected Classes
Fair Representation Clustering with Several Protected Classes
复制标题
具有多个受保护类别的公平表示集群
DOI：
10.1145/3531146.3533146
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vakilian, Ali
中科院分区：
文献类型：
--
作者：
Dai, Zhen;Makarychev, Yury;Vakilian, Ali
我们研究的问题，公平的k-中位数，每个集群都需要有一个公平的代表性的个人从不同的群体。在公平表示k-中位数问题中，我们给出度量空间中的一组点X。每个点x ∈ X属于一个群。此外，我们给出了每个群j ∈ [n]的公平表示参数αj和βj。我们说k-聚类C1，Ck，Ck公平地表示所有组，如果聚类Ci中来自组j的点的数量在αj之间|CI|和βj| CI|对于所有j ∈ [k]和i ∈ [k]。目标是找到一组k个中心和一个分配，使得定义的聚类公平地表示所有的组，并且最小化目标函数∑x ∈ Xd（x，<$（x））.注意，用于该问题的已知算法或者（i）通过加性项违反公平性约束，或者（ii）在k和k都是指数的时间上运行。我们还考虑了一个重要的特殊情况下的问题，其中和所有j ∈ []。对于这种特殊的情况下，我们提出了一个O（log k）-近似算法，运行时间。
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, ⋅⋅⋅, 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 of k centers and an assignment such that the clustering defined by fairly represents all groups and minimizes the ℓ1-objective ∑x ∈ Xd(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 and for all j ∈ [ℓ]. For this special case, we present an O(log k)-approximation algorithm that runs in time.
登录
查看更多内容
DOI：
10.1145/3442188.3445906
发表时间：
2020-10
期刊：
Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency
影响因子：
--
作者：
Mehrdad Ghadiri;S. Samadi;S. Vempala
通讯作者：
Mehrdad Ghadiri;S. Samadi;S. Vempala
DOI：
--
发表时间：
2021-06
期刊：
ArXiv
影响因子：
--
作者：
Seyed-Alireza Esmaeili;Brian Brubach;A. Srinivasan;John P. Dickerson
通讯作者：
Seyed-Alireza Esmaeili;Brian Brubach;A. Srinivasan;John P. Dickerson
DOI：
--
发表时间：
2019-05
期刊：
--
影响因子：
--
作者：
Xingyu Chen;Brandon Fain;Charles Lyu;Kamesh Munagala
通讯作者：
Xingyu Chen;Brandon Fain;Charles Lyu;Kamesh Munagala
使用级联规范目标近似公平聚类
DOI：
10.1137/1.9781611977073.104
发表时间：
2022
期刊：
Proceedings of the ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Chlamtáč, Eden;Makarychev, Yury;Vakilian, Ali
通讯作者：
Vakilian, Ali
DOI：
--
发表时间：
2020-07
期刊：
--
影响因子：
--
作者：
Matthew D. Jones;Huy L. Nguyen;Thy Nguyen
通讯作者：
Matthew D. Jones;Huy L. Nguyen;Thy Nguyen