Approximation Algorithms for Socially Fair Clustering
Approximation Algorithms for Socially Fair Clustering
复制标题
DOI：
--
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Yury Makarychev;A. Vakilian
中科院分区：
文献类型：
--
作者：
Yury Makarychev;A. Vakilian
提出了一种以$\ell_p为目标的社会公平聚类的$(e^{O(P)}\FRAC{\log\ell})$-近似算法。在这个问题中，我们被赋予度量空间中的一组点。每个点属于一个(或多个)$\ell$组。我们的目标是找到一个同时对所有群体都有利的$k$-中值，$k$-意思是，或者更广泛地说，$\ell_p$-集群。更准确地说，我们需要找到一组$k$中心$C$，以便最小化所有组$j$中的$\sum_{u\Text{in group}j}d(u，C)^p$的最大值。社会公平集群问题是由Ghadiri、Samadi和Vempala[2021]以及Abbasi、Bhaskara和Venkatasubramanian[2021]独立提出的。我们的算法改进和推广了他们关于该问题的$O(\ell)$-近似算法。该问题的自然Lp松弛有一个$\Omega(\ell)$的积分间隙。为了得到我们的结果，我们引入了一个加强的Lp松弛，并证明了对于固定的$p$，它有$\theta(FRAC{\log\ell}{\log\log})$的积分间隙。此外，我们还给出了一个双准则逼近算法，它推广了Abbasi等人的双准则逼近。[2021][中英文摘要]。
We present an $(e^{O(p)} \frac{\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 $\sum_{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(\frac{\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].