arXiv cs.CL· M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott, Mingu Lee, Richard Lethin, Chris Lott, Roland Memisevic, Fatih Porikli·· 5 小时前AI 评分22
图粗化让计算受限的非凸 MAX-CUT 逃离局部最优
Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
AI 导读
研究提出用谱图粗化方法 CMG 为基于矩的非凸连续重构 PPR 提供热启动，在 t2g20（n=400）上平均达到最优解的 97.5%、最佳运行达 98.4%。加入离散局部搜索的扩展版本在近期神经分支定界方法评测的全部 60 个 Biq Mac 实例上达到已公布最优解。采用稀疏 CSR 表示后，该方法可扩展至最多 20,000 个顶点的 G-set 实例，内存需求最多降低 3333 倍。
来源：arXiv cs.CL · arxiv.org