AAAIFeb, 2019
细粒度搜索空间分类用于求解子集问题的困难枚举变体
Fine-grained Search Space Classification for Hard Enumeration Variants of Subset Problems
Juho Lauri, Sourav Dutta
TL;DR本文提出了一个简单，强大和灵活的机器学习框架，用于减少计算困难的集合问题的枚举变量搜索空间，并通过输入分布产生的信息提示来增强现有的最先进的求解器。我们将我们的框架实例化为图中列出所有最大团的问题，这是网络分析，数据挖掘和计算生物学中的中心问题。我们证明了我们的方法在具有数百万个顶点和边的真实世界网络上的实用性，不仅保留了所有最优解，而且还积极剪枝输入实例大小，导致比最先进的算法快几倍。最后，我们探讨了我们提出的框架的可扩展性和鲁棒性的限制，表明监督学习在实践中应用于 NP-hard 问题是可行的。