Approximating Fair Clustering with Cascaded Norm Objectives
Approximating Fair Clustering with Cascaded Norm Objectives
复制标题
使用级联规范目标近似公平聚类
DOI：
10.1137/1.9781611977073.104
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Vakilian, Ali
中科院分区：
文献类型：
--
作者：
Chlamtáč, Eden;Makarychev, Yury;Vakilian, Ali
我们介绍了（p，q）-公平聚类问题。在这个问题中，我们给出一组点P和一组不同的权函数W。我们希望找到一个聚类，它最小化W上的向量的范数和P中的点到中心的加权距离的范数。这推广了各种聚类问题，包括社会公平中值和k均值，并密切联系到其他问题，如Densestk-子图和Mink-联盟。我们利用凸规划技术来近似（p，q）-公平聚类问题的不同值的pandq。当p ≥q时，基于Mink-Union的严格性和其它问题，我们得到了一个O（k（p-q）/（2 pq）），它几乎匹配akΩ（（p-q）/（pq））下界.当q ≥p时，我们得到了一个近似，它与boundedp，q的输入大小无关，并且与Makarychev和Vakilian（COLT 2021）的（p，∞）-Fair Clustering的recentO（（logn/（log logn））1/p）-近似相匹配。
We introduce the (p, q)-Fair Clustering problem. In this problem, we are given a set of pointsPand a collection of different weight functionsW. We would like to find a clustering which minimizes theℓq-norm of the vector overWof theℓp-norms of the weighted distances of points inPfrom the centers. This generalizes various clustering problems, including Socially Fairk-Median andk-Means, and is closely connected to other problems such as Densestk-Subgraph and Mink-Union.We utilize convex programming techniques to approximate the (p, q)-Fair Clustering problem for different values ofpandq. Whenp≥q, we get anO(k(p–q)/(2pq)), which nearly matches akΩ((p–q)/(pq))lower bound based on conjectured hardness of Mink-Union and other problems. Whenq≥p, we get an approximation which is independent of the size of the input for boundedp,q, and also matches the recentO((logn/(log logn))1/p)-approximation for (p, ∞)-Fair Clustering by Makarychev and Vakilian (COLT 2021).
登录
查看更多内容
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：
--
发表时间：
2019-05
期刊：
--
影响因子：
--
作者：
Xingyu Chen;Brandon Fain;Charles Lyu;Kamesh Munagala
通讯作者：
Xingyu Chen;Brandon Fain;Charles Lyu;Kamesh Munagala
社会公平聚类的 FPT 近似
DOI：
--
发表时间：
2021
期刊：
arXiv.org
影响因子：
--
作者：
Dishant Goyal;Ragesh Jaiswal
通讯作者：
Ragesh Jaiswal
DOI：
10.4230/lipics.approx-random.2016.6
发表时间：
2016-05
期刊：
ArXiv
影响因子：
--
作者：
E. Chlamtác;M. Dinitz;C. Konrad;G. Kortsarz;George Rabanca
通讯作者：
E. Chlamtác;M. Dinitz;C. Konrad;G. Kortsarz;George Rabanca
鲁棒 k 中值问题的新近似性结果
DOI：
--
发表时间：
2013
期刊：
Scandinavian Workshop on Algorithm Theory
影响因子：
--
作者：
Sayan Bhattacharya;Parinya Chalermsook;K. Mehlhorn;Adrian Neumann
通讯作者：
Adrian Neumann