  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_n\right\} \subset [0,
2\pi]$, 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.
