nicolasboumal/maxcut

Optimization algorithms to compute approximate solutions to the Max-Cut problem

Max-Cut

Optimization algorithms to compute approximate solutions to the Max-Cut problem

These are codes from 2016 used for the experiments in the following paper:

N. Boumal, V. Voroninski and A. S. Bandeira,

The non-convex Burer-Monteiro approach works on smooth semidefinite programs,

in the proceedings of NIPS 2016.

We followed up with more theory in another paper:

N. Boumal, V. Voroninski and A. S. Bandeira,

Deterministic guarantees for Burer-Monteiro factorizations of smooth semidefinite programs,

in Communications on Pure and Applied Mathematics, 2019.

Usage:

1. Install Manopt, SDPLR and CVX (or a subset, depending on which methods you want to test)
2. Make sure they are all on your Matlab path
3. Run rudytest.m for the actual experiments (edit it first to choose which graphs to run on etc.)
4. Run rudytest_to_table.m (this produces rudytable.tex with latex code for a table of results; without header though: see the paper)

Uploaded to github on March 25, 2024.