本研究提出了一种基于低度图的层次快速算法，可以在多项式空间复杂度内解决最大独立集问题，并得到了在不同最大度的图形中最大独立集问题的改进算法。

Dec, 2013

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

Aug, 2022

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

Jun, 2022

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

Oct, 2023

在回复评论者的回复中，我们指出其关注的最大独立集（MIS）在稀疏图中和贪心算法优秀表现无关，我们还强调了原始框架中广泛的算法开发，并通过提供额外的数值结果证明了我们原来的结果的可观改进，进而驳斥了评论中的性能声明。我们同时通过实验证明了我们提出的随机 d - 正则图不提供用于基准测试的通用实例集，贪心算法不提供通用算法基线。最后，我们指出图神经网络的内在（并行）解剖与贪心算法的（顺序）本质非常不同，并强调图神经网络已经展示出了比现有启发式方法（如并行退火）更高的可扩展性潜力。这份工作的概念创新值得探讨并有潜力进一步拓展。

Feb, 2023

我们描述了一种并行的近似算法，用于在分布式内存多处理器上最大化满足遗传约束的单调次模函数。

Mar, 2024

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

Mar, 2022

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

Aug, 2017

本文研究了最大子模函数匹配问题，给出了两种空间复杂度均为 O (nlogn) 的半流算法，并探讨了最大加权匹配和多重矩阵交叉的相似性，以求得更普适的解决方案。

Sep, 2013

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

Jul, 2008