Oct, 2018

解决实际大规模图中的最大权独立集问题

PDF
TL;DR本文提出了一种新的最大权独立集问题分支和缩减策略，结合核心化与局部搜索能够比局部搜索单独得出更高质量的解，通过实验表明，在实践中这种方法比现有的算法更加有效，可以处理高达数百万个顶点和边的实际问题。
np-hard optimizationbranch-and-reduce searchmaximum weight independent set problemreal-world graphskernelization
发现论文，激发创造
  • 大规模最大独立集问题的元启发式算法

    针对实际的车辆路径问题，研究了最大权独立集问题，通过开发一个新的本地搜索算法，该算法使用了先前文献中未描述的更广泛的简单局部搜索运算和数据结构，引入了路径重新链接的新变体来避免局部最优解以及一种新的交替增广路径局部搜索移动来提高算法性能。

    Mar, 2022

  • H - 自由图中最大权独立集问题的拟多项式时间逼近方案

    本文研究的是在 $H$-free 图中最大独立集问题的复杂度，通过提出近似算法和精确算法，对一些情况下的这一问题做出了更好的可解性结果。

    Jul, 2019

  • 大规模寻找近似最优独立集

    本文提出一种应用进化算法和核技术求解大规模稀疏网络独立集问题的高效算法，并通过移除可能出现在大独立集中的顶点来加速计算，并在此基础上在比文献中更大的实例上计算高质量的独立集。

    Sep, 2015

  • 最大独立集的可扩展核化算法

    本文提出一种基于图分割和并行二分图最大匹配的高效并行核化算法，通过依赖检查和约简跟踪技术加速核化，能够同时快速生成小内核，以及找到最小内核并加速发现最大独立集，取得比现有最快算法更小的内核大小和类似执行时间的优势。

    Aug, 2017

  • 最大独立集问题的自适应重复交集约简局部搜索

    本文研究了应用广泛的 NP-hard 问题之一，最大独立集问题（ M IS），提出了局部搜索框架 ARIR 及其三种算法，采用三种不同的减少策略，在五组基准测试中显示出明显的优越性。

    Aug, 2022

  • 深度学习在组合优化树搜索中的问题

    本研究提出了一个开源基准套件，对最大独立集问题进行了深入分析，结果表明现有的机器学习算法未能学习最优解的结构，算法技术仍是获得有效解决方案的关键。

    Jan, 2022

  • 最大权独立集的消息传递

    探讨在图中找到最大独立集的最大权重问题中使用信息传递算法的方法，并介绍了经典的 max-product 信念传播算法的性能，以及最大化固定点的自然初始化方法对算法收敛的影响。同时发现，在概率分布的 MAP 估计问题中，可以将任何问题都简化为 MWIS 问题，从而为 MAP 估计提供新的洞见和算法。

    Jul, 2008

  • 现代图神经网络在解决诸如最大独立集等组合优化问题方面表现不如传统的贪心算法

    该论文引入了一种物理启发的无监督图神经网络以解决稀疏图上的组合优化问题，作者展示了在最大割和最大独立集问题上这些 GNNs 的性能可以与或优于现有求解器，并且具有处理百万变量问题的能力。然而，该评论提出了一个简单贪心算法可以找到比 GNN 更好的质量的解决方案。此外，该评论者还建议通过基于真正困难的问题的标准基准测试未来的神经网络优化器。

    Jun, 2022

  • 最大独立集合的最佳低阶硬度

    研究在稀疏的 Erdős-Rényi 随机图中寻找大独立集的算法任务，其中低次多项式算法可以找到半优大小的独立集，但不大于此规模。

    Oct, 2020

  • 最大独立集：动态规划自学习

    本文提出了一种基于动态规划的图神经网络（GNN）框架来解决最大独立集（MIS）问题，通过递归算法构建子图并预测具有较大 MIS 的子图，进而在下一个递归调用中使用。我们通过对不同图形之间的 MIS 大小进行注释比较来训练算法，注释比较的输出结果用于自我训练过程，以提高注释比较的准确性。我们提供了在多个合成和真实数据集中证明我们算法优越性的数值证据。

    Oct, 2023