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

M. Harper Langston, Pierre-David Letourneau, Dalton Jones +7

Because its binary optimization landscape contains exponentially many local optima, MAX-CUT is highly sensitive to initialization. We study Particle Polynomial Relaxation (PPR), a…