Max-Cut via Kuramoto-Type Oscillators
Stefan Steinerberger · SIAM Journal on Applied Dynamical Systems · 2023
Abstract. We consider the Max-Cut problem. Let [Formula: see text] be a graph with adjacency matrix [Formula: see text]. Burer, Monteiro, and Zhang proposed to find, for [Formula: see text] angles [Formula: see text], minima of the energy [Formula: see text]. Configurations achieving a global minimum leads to a partition of size at least [Formula: see text]. This approach is known to be computationally viable and leads to very good results in practice. We prove, for each [Formula: see text], that replacing [Formula: see text] with an explicit [Formula: see text] global minima lead to a partition of size at least [Formula: see text]. This suggests some interesting algorithms that perform well. It also shows that the problem of finding approximate global minima of energy functionals of this type is NP-hard, in general.