arXiv cs.LG· M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott, Mingu Lee, Richard Lethin, Chris Lott, Roland Memisevic, Fatih Porikli·· 19 天前AI 评分32
图粗化助力算力受限的非凸 MAX-CUT 逃离局部最优
Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
AI 导读
研究人员提出结合组合多重网格（CMG）谱图粗化与粒子多项式松弛（PPR）的非凸优化流程，用于解决 MAX-CUT 初始化敏感问题。在 t2g20 基准上，CMG+PPR 平均达到最优解的 97.5%，加入离散局部搜索微调后在全部 60 个 Biq Mac 算例上均达到已知最优解。借助稀疏 CSR 表示，该方法可扩展至达 20,000 个顶点的 G-set 算例，显存占用最多减少 3333x。
来源：arXiv cs.LG · arxiv.org