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·· 3 天前AI 评分22
图粗化让计算受限非凸 MAX-CUT 逃离局部最优
Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT
AI 导读
研究将谱图粗化方法 CMG 用于热启动 Particle Polynomial Relaxation（PPR），在 t2g20（n=400）上平均达到最优解的 97.5%、最佳运行 98.4%。
正文 · AI 翻译
摘要：由于其二值优化景观包含指数级数量的局部最优解，MAX-CUT 对初始化高度敏感。我们研究粒子多项式松弛（PPR），这是一种基于矩的非凸连续重构，具有有利的优化景观。我们用组合多重网格（CMG）对 PPR 进行热启动，CMG 是一种谱图粗化方法，可在近线性时间内生成结构感知的初始解，且无需训练数据。在具有已知精确最优值的基准实例 \texttt{t2g20}（$n=400$）上，CMG+PPR 组合流程平均达到最优值的 $97.5\%$，最佳运行达到 $98.4\%$。带有离散局部搜索精化的扩展变体在最近一种神经分支定界方法评估的全部六十个 Biq Mac 实例上均达到已发表的最优值。使用稀疏 CSR 表示，同一方法可扩展到多达 $20{,}000$ 个顶点的 G-set 实例，将内存需求降低多达 $3333\times$，同时保持对 CMG 热启动的持续改进。增益在稀疏加权图上最大；在稠密图上，我们用谱稀疏化来补充该流程。
| 主题： | 机器学习（cs.LG）；人工智能（cs.AI）；计算与语言（cs.CL）；数值分析（math.NA）；优化与控制（math.OC） |
| 引用为： | arXiv:2610.19043 [cs.LG] |
| （或 arXiv:2610.19043v1 [cs.LG] 用于此版本） | |
| https://doi.org/10.48550/arXiv.2610.19043 由 DataCite 颁发的 arXiv DOI（待注册） |
|
| 期刊 参考： | OPT2026（Neurips Workshop） |
提交历史
来自：M. Harper Langston [查看电子邮件]
[v1]
2026年10月13日星期二 18:32:31 UTC（1,689 KB）
来源：arXiv cs.CL · arxiv.org