Nov, 2011

快速平衡划分尽管在网格和树上也很困难

PDF
TL;DR本文探讨了 k-Balanced Partitioning 问题的两类近似算法：快速但准确度不高和保证高质量准确度但速度较慢的算法。研究表明，这种运行时间和解决方案质量之间的权衡是必要的。我们还提出了一种基于图形类别的规约框架，以证明了该问题的困难性。本文是该问题的第一次双层次不可近似结果。
k-balanced partitioningapproximation algorithmsgraph theorynp-hardnessbicriteria inapproximability
发现论文，激发创造
  • 通过最优输运实现任意尺寸约束的图割

    通过提出一种基于正则化 Gromov-Wasserstein 问题的加速近端梯度下降算法，我们解决了图切割问题，并实现了稀疏解，相较于经典谱聚类算法，额外的复杂度仅为 O (log (n))，但效率更高。

    Feb, 2024

  • GAP: 通用的近似图分区框架

    本研究提出了基于深度学习的 GAP 框架来解决节点分割问题。通过定义不同 iable 损失函数以及利用反向传播来优化网络参数，实现基于图结构的节点分割。相较于传统的分割方法，GAP 不仅更快，并且具有良好的扩展性能力，可适用于不同的图结构，并可推广到未知的图形结构上。研究表明，GAP 能够取得与传统分割方式相媲美的结果。

    Mar, 2019

  • 有效局部搜索增强平衡图边划分

    本文研究了图分区中的边划分问题，提出了可调节的边和块的两个新概念，基于此发展了一种贪心启发式和一个利用最大流模型的改进搜索算法，可以大幅度提高图分区的质量和近似比。

    Dec, 2020

  • 一种超出最坏情况的图聚类的近线性时间逼近算法

    在半随机图模型中，我们研究了平衡切割问题的精确性和时间复杂度，并且提出了第一个近似线性时间算法，以及与相关问题的拓展应用和对半随机分层随机块模型的聚类目标函数进行近似线性时间 O (1) 近似的方法。

    Jun, 2024

  • 使用自适应分割的分类算法

    提出了一种使用装饰树的自适应树划分算法，可以生成更高阶方法的估计集以及在平滑度和边际条件方面具有更强的收敛性。

    Nov, 2014

  • 多维均衡图分割的投影梯度下降算法

    我们研究了多维平衡图分区问题，提出一种基于随机投影梯度下降的可扩展技术来解决该问题，并在实验中表明该方法在大规模图处理时具有卓越的性能表现。

    Feb, 2019

  • 大规模图的本地聚类算法及其在近似线性时间图分割中的应用

    本文研究了大规模图的本地算法设计并提出了一种本地聚类算法，该算法可在几乎线性的时间内找到较好的簇，并基于该聚类算法提出了一种划分算法，进而设计了求解对称对角占优矩阵中线性系统的近线性算法，还提出了其他相关结果。

    Sep, 2008

  • 流式图挑战：随机块划分

    实现大规模图表分析的基础是合理的分区算法，本文提出了一种基于贝叶斯推断方法的分区算法，并介绍了数据集、并行计算、评估指标等多个方面，最终展示了其高效性。

    Aug, 2017

  • 基于优先级的平衡图分区再流算法

    介绍了一种新型的基于 restreaming 的算法，使用带有乘性权重的约束管理策略来优化流式过程的排序，同时借鉴了平衡标签传播的优先级概念来进行分区优化，得到了与现有算法相比在真实世界图上具有更好性能的结果。

    Jul, 2020

  • 近似扩张剖面和几乎最优局部图聚类

    本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

    Apr, 2012