多样性感知聚类：计算复杂度和近似算法 | BriefGPT - AI 论文速递

Jan, 2024

多样性感知聚类：计算复杂度和近似算法

Diversity-aware clustering: Computational Complexity and Approximation Algorithms

Suhas Thejaswi, Ameet Gadekar, Bruno Ordozgoiti, Aristides Gionis

TL;DR在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $k$-median、$k$-means 或 $k$-supplier。我们提出了参数化逼近算法，逼近比例分别为 $1+ rac {2}{e}$、$1+rac {8}{e}$ 和 $3$，用于多样性感知 $k$-median、多样性感知 $k$-means 和多样性感知 $k$-supplier。这些逼近比例在假设 Gap-ETH 和 FPT $ eq$ W [2] 的情况下是紧密的。对于公平 $k$-median 和公平 $k$-means 与不相交设施组，我们分别提出了参数化逼近算法，逼近比例为 $1+rac {2}{e}$ 和 $1+rac {8}{e}$。对于公平 $k$-supplier 与不相交设施组，我们提出了一个多项式时间逼近算法，其因子为 $3$，改进了先前已知的逼近比例因子为 $5$。

Abstract

In this work, we study diversity-aware clustering problems where the data points are associated with multiple attributes resulting in intersecting groups. A clustering solution need to ensure that a minimum number of cluster centers are chosen from each group while simultaneously minim

diversity-aware clustering approximation algorithms k-median k-means k-supplier

发现论文，激发创造

社会公平的常积分因子 $k$- 聚类近似算法

本研究对含 m 个群体的社会公平 (l_p, k)- 聚类问题的近似算法进行研究，其中特殊情况包括社会公平 k - 中心 (p=1) 和社会公平 k - 均值 (p=2) 问题。研究分别给出了多项式时间和两种不同的 (n^{2^{O (p)} m^2} 和 k^m poly (n)) 的近似算法，并探讨了这些算法与现有算法的比较。

Jun, 2022

公平范围聚类的近似算法

研究公平间距聚类问题，提供 O (1) 的近似算法在最多 k+2l 个中心中选择最小化聚类成本的一组中心，并仅在每个人口统计上最多违反 2 个加法项的上限。

Jun, 2023

聚类与多样性

本文主要讨论聚类算法在数据发布中的应用，特别是隐私保护，作者提出了一种 2 近似算法来解决按照颜色进行分组聚类的问题并讨论了其优化和推广。

Apr, 2010

个体公平聚类的改进近似算法

此论文介绍了一种可行的算法，用于从簇成员与簇中心之间的距离范数角度出发解决公平聚类问题，并对相应指标（如 bicriteria）进行了优化；同时，提供了一种基于模类约束的距离范数成本设施位置 16^p - 近似算法，并将借鉴此算法，将个体公平聚类转化为更一般如群体公平聚类的解法。

Jun, 2021

论基本公平聚类的代价

本文提出了针对多个保护类的公平聚类方法，并且提出了一种松散的公平概念，在这种概念下，可以对所有经典聚类目标进行双标准常数因子近似，这是通过将任意现有不公平的（整数）解和公平的（分数）线性规划解结合起来实现的。

Nov, 2018

对成对公平 $k$- 中位聚类问题的多项式时间近似

我们研究了配对公平聚类，其中对于每个聚类和每个组，来自组 i 的聚类 C 中的点的数量必须不超过其他组 j 中的点的数量的 t 倍，我们设计了第一个满足公平性约束条件的多项式时间近似算法，并提供了近似难度的结果。

May, 2024

社会公正聚类的近似算法

本文提出了一种在社会公正聚类中的近似算法，这个问题包括了在一个度量空间中，给定一组点，每个点属于一个或多个组，为了同时满足所有组，需要找到一个 k - 中位数、k - 均值或者更一般意义上，l_p - 聚类，同时给出了强化的 LP 松弛，将其应用于近似算法和双标准近似算法，并取得了理论上的改进。

Mar, 2021

差分隐私聚类：紧密逼近比率

本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。

Aug, 2020

KFC：$k$- 中心公平聚类的可扩展近似算法

探讨了关于 $k-$center 目标函数的公平聚类问题，使用保护组的概念确保每个簇的公平性，提出了一种新的随机化 $3-$ 近似算法，对比之前的算法在效率和公平性方面获得了优化。

Oct, 2020

离散几何空间中鲁棒聚类的参数化逼近

本文介绍了 Robust k-z 聚类和其在度量空间、算法公平性、欧几里得空间和 FPT 近似等领域的应用，提出了相应的算法，其中在特殊的欧几里得空间中得到了较好的近似结果。

May, 2023