论文标题
社会上公平的$ k $ clustering的恒定因素近似算法
Constant-Factor Approximation Algorithms for Socially Fair $k$-Clustering
论文作者
论文摘要
我们研究了社会上公平$（\ ell_p，k）$的近似算法 - $ m $组的聚类问题，其特殊案例包括社会公平的$ k $ -Median（$ p = 1 $）和社会公平的$ k $ - $ - $ -Means（$ p = 2 $）问题。我们提出（1）多项式时间$（5+2 \ sqrt {6}）^p $ - approximation，最多$ k+m $中心（2）a $（5+2+2 \ sqrt {6}+ε）^p $ - approximation^p $ - $ k $ a $ k $ in PIME $ n^^2^2^2^2^{p） a $（15+6 \ sqrt {6}）^p $近似为$ k $中心$ k^{m} \ cdot \ text {poly}（n）$。第一个结果是通过使用一系列线性程序的迭代舍入方法的改进来获得的。后两个结果是通过将最多$ K+M $中心的解决方案转换为使用（2）的稀疏方法的$ K $中心的解决方案，并通过详尽的搜索（3）。我们还将算法的性能与现有的双色算法以及基准数据集中的$ K $中心近似算法的确切性能进行了比较，并发现我们的算法在实践中也优于现有方法。
We study approximation algorithms for the socially fair $(\ell_p, k)$-clustering problem with $m$ groups, whose special cases include the socially fair $k$-median ($p=1$) and socially fair $k$-means ($p=2$) problems. We present (1) a polynomial-time $(5+2\sqrt{6})^p$-approximation with at most $k+m$ centers (2) a $(5+2\sqrt{6}+ε)^p$-approximation with $k$ centers in time $n^{2^{O(p)}\cdot m^2}$, and (3) a $(15+6\sqrt{6})^p$ approximation with $k$ centers in time $k^{m}\cdot\text{poly}(n)$. The first result is obtained via a refinement of the iterative rounding method using a sequence of linear programs. The latter two results are obtained by converting a solution with up to $k+m$ centers to one with $k$ centers using sparsification methods for (2) and via an exhaustive search for (3). We also compare the performance of our algorithms with existing bicriteria algorithms as well as exactly $k$ center approximation algorithms on benchmark datasets, and find that our algorithms also outperform existing methods in practice.
