We consider the Max-Cut problem. Let $G = (V,E)$ be a graph with adjacency matrix $(a_{ij})_{i,j=1}^{n}$. Burer, Monteiro & Zhang proposed to find, for $n$ angles $left{theta_1, theta_2, dots, theta_nright} subset [0, 2pi]$, minima of the energy $$ f(theta_1, dots, theta_n) = sum_{i,j=1}^{n} a_{ij} cos{(theta_i - theta_j)}$$ because configurations achieving a global minimum leads to a partition of size 0.878 Max-Cut(G). This approach is known to be computationally viable and leads to very good results in practice. We prove that by replacing $cos{(theta_i - theta_j)}$ with an explicit function $g_{varepsilon}(theta_i - theta_j)$ global minima of this new functional lead to a $(1-varepsilon)$Max-Cut(G). 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.
Download