pipette
ENEnglish

Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

M. Harper Langston, Pierre-David Letourneau, Dalton Jones, Harris Teague, Peter Scott, Mingu Lee, Richard Lethin, Chris Lott, Roland Memisevic, Fatih Porikli

Preprint con versión publicada

En palabras de los autores

Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. We study Particle Polynomial Relaxation (PPR), a moment-based nonconvex continuous reformulation possessing an advantageous optimization landscape. We warm-start PPR with Combinatorial Multigrid (CMG), a spectral graph-coarsening method that produces structure-aware initial solutions in near-linear time without training data. On t2g20 (), benchmark instance with known exact optimum, the combined CMG+PPR pipeline reaches of optimum on average and on the best run. An extended variant with discrete local-search refinement reaches the published optimum on all sixty Biq Mac instances evaluated by a recent neural branch-and-bound method. Using a sparse CSR representation, the same approach scales to G-set instances with up to vertices reducing memory requirements by up to while maintaining a consistent improvement over the CMG warm start. Gains are largest on sparse weighted graphs; on dense graphs we complement the pipeline with spectral sparsification.

Resultado principalLimitación que admiten los autores

Apareció: jueves, 15 de octubre. arXiv. Preprint con versión publicada.

Versión publicada: OPT2026 (Neurips Workshop)