4
$\begingroup$

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

Improve this question
$\endgroup$
13
  • 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, 2019 at 14:51
  • 1
    $\begingroup$ Sure, please post! $\endgroup$
    – Aryeh
    Mar 14, 2019 at 16:15
  • 4
    $\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, 2019 at 16:58
  • $\begingroup$ @NealYoung Is the model you are suggesting equivalent to SDP? Can every situation be visualized analogously? Where did the model you suggest arise? $\endgroup$
    – Turbo
    May 12, 2021 at 12:08
  • $\begingroup$ @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. $\endgroup$
    – Neal Young
    May 12, 2021 at 13:00

1 Answer 1

Reset to default
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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