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

DOI10.48550/arXiv.2610.19043MaRDI QIDQ7395260arXivFDO

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

Publication date 13 October 2026

Published in arXiv

Tldr The paper proposes using graph coarsening as a preprocessing step for optimizing nonconvex MAX-CUT formulations, leading to significant improvements in optimality gap and efficiency. The approach is particularly effective on sparse graphs, where it reduces memory requirements by up to 3333x while maintaining consistent gains over the baselines.

Full work available at URL https://doi.org/10.48550/arXiv.2610.19043

arXiv classification

cs.AIcs.CLcs.LGmath.NAmath.OC

Cites work

• A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
• A genetic algorithm for the multidimensional knapsack problem
• A Gentle Introduction to Memetic Algorithms
• A method for solving traveling-salesman problems
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• A Stochastic Approximation Method
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• An Efficient Framework for Global Non-Convex Polynomial Optimization over the Hypercube
• An Efficient Heuristic Procedure for Partitioning Graphs
• Future paths for integer programming and links to artificial intelligence
• Global optimization with polynomials and the problem of moments
• Graph Sparsification by Effective Resistances
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Learning-augmented streaming algorithms for approximating MAX-CUT
• On the limited memory BFGS method for large scale optimization
• Parallelizing the dual revised simplex method
• Reducibility among combinatorial problems
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Tabu search
• The Mixing method: low-rank coordinate descent for semidefinite programming with diagonal constraints
• The non-convex Burer-Monteiro approach works on smooth semidefinite programs

This page was built for publication: Graph Coarsening Enables Escaping Local Optima in Compute-Constrained Nonconvex MAX-CUT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7395260)