Jul, 2023

多项式对数轮次内求解相关聚类问题的三因素近似算法失效

PDF
TL;DR本文研究了用于相关聚类问题的并行算法，其中每个不同实体的每对实体都标记为相似或不相似，旨在将实体分成簇以最小化与标签的不一致性，提出了首个多项式对数深度并行算法，并使用比 3 更好的逼近比计算 (2.4 +ϵ) 逼近解，可以将其转换为 (m1.5) 时间顺序算法和带有 (m1.5) 总内存的多项式对数轮次亚线性内存计算算法。
parallel algorithmscorrelation clusteringapproximation ratiopoly-logarithmic depthlinear program
发现论文，激发创造
  • 完全图和完全 k 部分图上相关聚类的近似最优线性规划舍入算法

    该论文提出了一种新的线性规划松弛四舍五入方案，解决了相关聚类问题的近似算法问题和完整性间隙问题，从而在完全图中实现了 2.06-ε 的近似度，而在完全 $k$- 部分图中实现了 3 的近似度。

    Dec, 2014

  • 通过强三元闭包标记的相关聚类：快速近似算法和实用下界

    本研究提出了更快的近似算法，避免了其最佳逼近算法所依赖的不切实际的线性规划放宽，为两个经过充分研究的特殊情况 —— 聚簇编辑和聚簇删除提供了更快、更实用、更高效的线性规划算法及极具可扩展性的组合技术，包括聚簇删除的第一个组合逼近算法，实际应用中，我们的算法产生了近乎与质量最佳算法相匹配的近似解，同时适用于数量级更大的问题。

    Nov, 2021

  • 常数轮并行下的相关聚类

    本文提出了一种基于大规模并行计算 (MPC) 的算法，用于解决相关聚类问题。该算法的主要目标是利用签名图对图进行分区以最小化争议数量。在实验中，该算法同时试图减少节点内存的使用率。我们的算法是第一个在亚线性存储器中运行且使用有限的 MPC 轮数可以证明近似计算聚类问题方法的一种。

    Jun, 2021

  • 大规模图上的并行相关聚类

    本文提出了 C4 和 ClusterWild！两个用于并行相关聚类的算法，并在实验中证明了它们在精度和运行时间方面的优势。

    Jul, 2015

  • 相关聚类推广

    LambdaCC 和 MotifCC 是两种变体的相关聚类问题，应用于网络分析和社区检测，我们提出了两种非平凡的逼近算法来解决该问题，其中我们提出了两个算法来改善先前的逼近结果，同时还研究了在构造两个簇的限制下的逼近结果，其中 MotifCC 应用于超图设置。

    Sep, 2018

  • 高效查询相关聚类

    本文主要研究了查询效率，使用类似于计算距离的相似度度量，通过提出新的算法实现了更加高效的相关聚类，能够在给定预算内使用不同的查询方式获得与最优解相差不大的结果，并且针对算法进行了实验研究。

    Feb, 2020

  • 多层关联聚类

    我们在这篇论文中建立了多层相关聚类，这是对相关聚类（Bansal 等人，FOCS'02）在多层设置中的一种新的概括。我们首先设计了一个基于知名区域生长技术的 O (Llogn) 逼近算法（其中 L 是层数），然后研究了带有概率约束的一个重要特殊情况。我们进一步设计了一个 4 逼近算法，该算法改进了一般概率约束情况下的逼近比例。使用真实数据集的计算实验证明了我们所提出算法的有效性。

    Apr, 2024

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

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

    Jun, 2022

  • 用于相关聚类的单遍基准算法。保持简单！

    本文介绍了 Correlation Clustering 中使用的 Pivot 算法的改进版本，并通过在单通道中使用 O (n/epsilon) 字的内存实现了 (3+epsilon) 近似，并与以前的结果进行了比较。

    May, 2023

  • 最小最大相关聚类的 4 近似算法

    我们介绍了一种用于最小最大相关聚类问题的下界技术，并基于此技术提出了一种完全图的组合 4 近似算法。我们通过贪婪连接启发式算法扩展了这个算法，并在几个基准数据集上实证表明它提高了解决方案的质量和运行时间，改进了现有的技术水平。

    Oct, 2023