论文标题
ARES：一种具有经常性评估和采样驱动推断的有效算法，用于最大独立集
ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set
论文作者
论文摘要
最大独立集（MIS）问题是一个众所周知的NP完整问题，在各个领域的广泛应用中。启发式方法通常用于有效解决此问题的大量实例，在合理的时间内产生高质量的解决方案。但是，启发式方法面临挑战，例如落入本地最佳选择和解决方案空间内的冗余搜索。本文介绍了一种有效的MIS问题启发式算法，并结合了两种创新技术。第一种技术具有经常性的评估机制，该机制可以监视解决方案的进度并识别局部优势，从而触发重新启动以避免对次优结果收敛。第二种技术利用采样驱动的推理规则根据采样解决方案进行选择性修复顶点，从而缩小搜索空间并提高效率。跨多个良好现实世界基准进行的全面实验评估表明，在解决方案质量，计算效率和稳定性方面，提出的算法优于最先进的算法。
The Maximum Independent Set (MIS) problem is a well-known NP-complete problem with a wide range of applications across various fields. Heuristic approaches are commonly utilized to efficiently tackle large instances of this problem, yielding high-quality solutions within a reasonable time. However, heuristics face challenges such as falling into local optima and redundant searches within the solution space. This paper introduces an efficient heuristic algorithm for the MIS problem, incorporating two innovative techniques. The first technique features a recurrent evaluation mechanism that monitors the progress of solutions and identifies local optima, triggering restarts to avoid convergence on suboptimal outcomes. The second technique utilizes a sampling-driven inference rule to selectively fix vertices based on sampled solutions, thereby narrowing the search space and enhancing efficiency. Comprehensive experimental evaluations across multiple well-established real-world benchmarks demonstrate that the proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.
