# Intuitive explanation behind Goemans-Williamson randomized rounding

A very simple randomized cut algorithm achieves $$1/2$$ of the optimal value: just choose each vertex to be in the cut with probability $$1/2$$, independently. Goemans-Williamson does something more sophisticated: first, they do a semi-definite relaxation to obtain $$n$$ unit vectors $$X_i$$ (rather than the $$n$$ bits $$x_i$$ that the original integer program MAXCUT is supposed to solve for), and then each vector $$X_i$$ is converted to a random bit by seeing what side of a random hyperplane $$g\sim N(0,I_n)$$ it falls on.

Intuitively, the new random variables $$\mathrm{sign}(X_i\cdot g)$$ are no longer independent -- unlike the naive randomized cut, where each vertex was chosen independently. I can see why creating dependencies might be beneficial: if a given vertex $$i$$ is chosen to be in the cut and has a large degree, then perhaps we might not want its neighbors to be in the cut. Is there an intuitive explanation behind the kind of dependencies that Goemans-Williamson rounding is creating between the vertices and why these are beneficial for obtaining larger cuts? [I understand the formal proof, which is relatively simple and very slick. Looking for intuition!]

• One view is to imagine $(Z_1, \ldots Z_n) \in \{-1, +1\}^n$ is a random optimal max-cut solution. WLOG $\mathbb{E} Z_i = 0$ for all $i$. Then you can view the GW SDP as an oracle telling you $\mathbb{E}[Z_i Z_j]$ for all $i$ and $j$. So the rounding solves the problem "if I only told you the mean and the covariance matrix of some unknown distribution on solutions, can you reconstruct a distribution on solutions which is approximately at least as good?" If this is helpful, I can post a short answer with some pointers to papers that elaborate on this viewpoint. – Sasho Nikolov Mar 14 '19 at 14:51
• Sure, please post! – Aryeh Mar 14 '19 at 16:15
• To build a geometric/physical intuition for the underlying optimization problem, view it as follows. (1) Embed the vertices of the graph on the surface of the (n-1)-sphere, while (2) maximizing the sum, over the edges, of the squared distances of the endpoints. Or, equivalently (2) replace each edge by a spring that repels its endpoints with force equal to the distance between its two endpoints, then let it evolve to reach a minimum-energy configuration. Play with example graphs with 3 or 4 vertices to understand the gradients and whatnot. (Beware: this representation is not convex, tho.) – Neal Young Mar 14 '19 at 16:58