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!]

  • 4
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Mar 14 at 14:51
  • 1
    $\begingroup$ Sure, please post! $\endgroup$ – Aryeh Mar 14 at 16:15
  • 3
    $\begingroup$ 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.) $\endgroup$ – Neal Young Mar 14 at 16:58

Great intuitive explanations above by Sasho Nikolov and Neal Young. Here's another one Eden Chlamtáč emailed in:

Well, the intuition is that the SDP solution assigns greater weight in the objective function to edges whose endpoints that are placed farther apart in the vector solution, so it makes sense to cluster the set of vertices geometrically into two contiguous sets. A random hyperplane is the simplest way of doing that, and it happens to work well.

  • $\begingroup$ There seems there should be some kind of information theoretic interpretation here. Is there some possibility? $\endgroup$ – Brout Mar 15 at 18:40
  • $\begingroup$ This seems like a purely computational problem to me -- where do you see information theory entering? $\endgroup$ – Aryeh Mar 16 at 18:03

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.