Feb, 2015

欧几里得 k - 均值问题的近似难度

PDF
TL;DR本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。
euclidean k-means problemnp-hardnessapproximation algorithmsspectral analysistriangle-free graphs
发现论文，激发创造
  • k-means 问题的改进与简化无法近似性

    研究了 k-means 问题在 Euclidean 空间中寻找 k 个中心使得所有点到离它们最近中心的距离平方和最小，证明了该问题的近似难度是 NP-hard，并且提出了最小近似系数 1.0013。

    Sep, 2015

  • 基于原始对偶算法的 k-Means 和欧几里得 k-Median 的更好保证

    该研究采用原始 - 对偶算法来解决 $k$-means 聚类问题，在满足集群数量限制的同时得到了 6.357 - 近似比的效果，并在欧几里得度量中解决了 $k$-median 的问题。

    Dec, 2016

  • 局部搜索在双倍指标下为 k-Means 提供 PTAS

    使用局部搜索启发式策略，本文证明了在任何固定维度的欧几里得空间中，k-means 问题均可提供 PTAS。

    Mar, 2016

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

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

    May, 2023

  • 欧几里得 k-means 的稳定实例聚类

    本文研究在实际应用中，哪些加性扰动稳定性的实例可以设计有效算法，并证明它们能找到最优聚类。我们提出了一种稳定性定义，并设计了算法以证明稳定实例的最优聚类。当实例具有一定的分离性时，我们显示出一种具有证明保证的鲁棒算法，也能容忍异常值。通过研究真实数据集的稳定性，我们补充了这些结果，并展示了我们的算法在这些基准数据集上的表现。

    Dec, 2017

  • 图上 k - 中心问题的动态算法

    提供了首个对动态图进行边更新的 k - 中心问题的高效算法

    Jul, 2023

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

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

    Jun, 2022

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

    在这项研究中，我们研究了多样性感知聚类问题，其中数据点与多个属性相关联，导致交叉组。聚类解决方案需要确保从每个组中选择最少数量的聚类中心，同时最小化聚类目标，可以是 $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$。

    Jan, 2024

  • 带有约束条件的隐私保护聚类

    探讨如何将具有某些限制的聚类问题的近似算法转化为更符合隐私约束的近似算法，并结合隐私与其他约束条件。

    Feb, 2018

  • 近线性时间内对倍增度量聚类的近似算法

    针对度量空间中的经典设施定位、$k$- 中位数和 $k$- 均值问题，我们提供了近线性时间的逼近方案，并展示了针对各种变型问题的技术扩展。

    Dec, 2018