An interesting problem has come up in my work, and I haven't quite been able to find references to it so I thought I'd ask here.


Suppose we have some complete, weighted graph with vertex set $V$. Is there an algorithm to partition $V$ into $V\_1, V\_2$ such that the sum of the edge weights going between the two sets is maximized (or some approximation thereof)?



Partitioning vertex set to maximize weights of inter-class edges?
This is the [weighted MAX CUT](https://en.wikipedia.org/wiki/Maximum_cut) problem, and it is NP-hard to compute exactly. Note that the case of $\{0,1\}$-weights corresponds to computing a MAX CUT in an arbitrary graph. This later problem has a beautiful polynomial-time approximation algorithm via semidefinite programming due to Goemans and Williamson, with an approximation ratio of $\alpha \approx 0.878$. Under the Unique Games Conjecture, this ratio is best possible. 


