# 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. Mar 14 '19 at 14:51
• Sure, please post! 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.) Mar 14 '19 at 16:58
• @NealYoung Is the model you are suggesting equivalent to SDP? Can every situation be visualized analogously? Where did the model you suggest arise?
– Mr.
May 12 at 12:08
• @1.. The optimization problem I described is equivalent to the GW SDP for max cut, in that there is a cost-preserving bijection between the feasible solutions. It is not a good formulation to work with directly though because it is not convex -- it can have local maxima that are not global maxima. The bijection is the standard mapping that takes a semi-definite matrix M to a set of vectors {V_i} where M_{ij} = V_i . V_j, which can be used for any SDP, and in that sense something similar works for any SDP. May 12 at 13:00