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

<p>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.</p>

CC BY-SA 4.0
2019-03-15T18:40:04.430Z
There seems there should be some kind of information theoretic interpretation here. Is there some possibility?
Turbo
CC BY-SA 4.0
2019-03-16T18:03:07.443Z
This seems like a purely computational problem to me -- where do you see information theory entering?
Aryeh
CC BY-SA 4.0
2019-03-15T09:31:33.747Z
2019-03-15T13:53:03.747Z
2019-03-15T13:53:03.747Z
Aryeh
<p>A very simple randomized cut algorithm achieves <span class="math-container">$1/2$</span> of the optimal value: just choose each vertex to be in the cut with probability <span class="math-container">$1/2$</span>, independently. Goemans-Williamson does something more sophisticated: first, they do a semi-definite relaxation to obtain <span class="math-container">$n$</span> unit vectors <span class="math-container">$X_i$</span> (rather than the <span class="math-container">$n$</span> bits <span class="math-container">$x_i$</span> that the original integer program MAXCUT is supposed to solve for), and then each vector  <span class="math-container">$X_i$</span> is converted to a random bit by seeing what side of a random hyperplane
<span class="math-container">$g\sim N(0,I_n)$</span>
 it falls on.</p>

<p>Intuitively, the new random variables <span class="math-container">$\mathrm{sign}(X_i\cdot g)$</span> 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 <span class="math-container">$i$</span> 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!]</p>

CC BY-SA 4.0
2019-03-14T14:51:31.330Z
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
CC BY-SA 4.0
2019-03-14T16:15:05.370Z
Sure, please post!
Aryeh
CC BY-SA 4.0
2019-03-14T16:58:05.197Z
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
CC BY-SA 4.0
2021-05-12T12:08:10.140Z
@NealYoung Is the model you are suggesting equivalent to SDP? Can every situation be visualized analogously? Where did the model you suggest arise?
Turbo
CC BY-SA 4.0
2021-05-12T13:00:40.903Z
@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.
Neal Young
CC BY-SA 4.0
2021-05-12T13:27:38.873Z
@NealYoung If it is not convex how did GW pull it off?
Turbo
CC BY-SA 4.0
2021-05-12T13:33:01.710Z
@1.. The semi-definite matrix representation is convex.  The vector representation is not.  SDP optimization is done with the semi-definite matrix representation.  For an analogy, consider a linear program such as $\min \{x_1 + x_2 : 0 \le x_1 \le 1, 0\le x_2 \le 1\}$.  By a change of variables it is equivalent to $\min \{\sqrt{y_1} + \sqrt{y_2} : 0\le y_1 \le 1, 0\le y_2 \le 1\}$.  But the latter representation is not convex.
Neal Young
CC BY-SA 4.0
2021-05-12T13:35:12.423Z
@NealYoung I see. The vector formulation is direct but not convex and the SDP formulation is a bijection which works. Too bad the vector formulation is a relaxation and there is no exact formulations in SDP. Do you know of any exact formulations is SDP? I would be interested in understanding.
Turbo
CC BY-SA 4.0
2021-05-12T13:38:34.203Z
@1... The vector formulation is not a relaxation, it captures all the constraints of the original SDP.  So in that sense it is "exact".  It is just not convex.  It is good for getting intuition though, e.g. for understanding the GW rounding.  I'm not sure what you mean by "exact" though.
Neal Young
CC BY-SA 4.0
2021-05-12T13:40:35.837Z
@NealYoung I think the vector is any vector on the sphere whose choice is dependent on global structure of the problem perhaps up to invariants related to the problem. BTW might I ask 'if UGC is false implies SDP can be improved' is known (the standard statement is following 'if UGC is correct SDP cannot be improved')?
Turbo
CC BY-SA 4.0
2021-05-12T13:42:13.093Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/124171/discussion-between-neal-young-and-1).
Neal Young
CC BY-SA 4.0
2021-05-12T19:53:19.583Z
@NealYoung I think optimal maxcut if we assume P\ne NP is 0.9.. but on UGC it is 0.878.. and so it cannot be known to be tight on P\ne NP assumption, Are you sure there are instances where factor is tight unconditionally or where UGC and P\ne NP ratios agree?
Turbo
CC BY-SA 4.0
2021-05-12T20:52:30.470Z
You mention there are multiple methods by which UGC might not be accurate. If there hypothetical methods you might be aware of?
Turbo
<approximation-algorithms><optimization><randomized-algorithms><max-cut>
Intuitive explanation behind Goemans-Williamson randomized rounding
Aryeh
# Intuitive explanation behind Goemans-Williamson randomized rounding

(Asked by: username_0 on 2019-03-14)

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

**Tags:** approximation-algorithms, optimization, randomized-algorithms, max-cut
> **Comments:**
> **username_1**: 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.  
> **username_0**: Sure, please post!  
> **username_2**: 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.)  
> **username_3**: @NealYoung Is the model you are suggesting equivalent to SDP? Can every situation be visualized analogously? Where did the model you suggest arise?  
> **username_2**: @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.  
> **username_3**: @NealYoung If it is not convex how did GW pull it off?  
> **username_2**: @1.. The semi-definite matrix representation is convex.  The vector representation is not.  SDP optimization is done with the semi-definite matrix representation.  For an analogy, consider a linear program such as $\min \{x_1 + x_2 : 0 \le x_1 \le 1, 0\le x_2 \le 1\}$.  By a change of variables it is equivalent to $\min \{\sqrt{y_1} + \sqrt{y_2} : 0\le y_1 \le 1, 0\le y_2 \le 1\}$.  But the latter representation is not convex.  
> **username_3**: @NealYoung I see. The vector formulation is direct but not convex and the SDP formulation is a bijection which works. Too bad the vector formulation is a relaxation and there is no exact formulations in SDP. Do you know of any exact formulations is SDP? I would be interested in understanding.  
> **username_2**: @1... The vector formulation is not a relaxation, it captures all the constraints of the original SDP.  So in that sense it is "exact".  It is just not convex.  It is good for getting intuition though, e.g. for understanding the GW rounding.  I'm not sure what you mean by "exact" though.  
> **username_3**: @NealYoung I think the vector is any vector on the sphere whose choice is dependent on global structure of the problem perhaps up to invariants related to the problem. BTW might I ask 'if UGC is false implies SDP can be improved' is known (the standard statement is following 'if UGC is correct SDP cannot be improved')?  
> **username_2**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/124171/discussion-between-neal-young-and-1).  
> **username_3**: @NealYoung I think optimal maxcut if we assume P\ne NP is 0.9.. but on UGC it is 0.878.. and so it cannot be known to be tight on P\ne NP assumption, Are you sure there are instances where factor is tight unconditionally or where UGC and P\ne NP ratios agree?  
> **username_3**: You mention there are multiple methods by which UGC might not be accurate. If there hypothetical methods you might be aware of?  

---

## 1 answers

### Answer by username_0 on 2019-03-15. Score: 2

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.

> **Comments:**
> **username_3**: There seems there should be some kind of information theoretic interpretation here. Is there some possibility?  
> **username_0**: This seems like a purely computational problem to me -- where do you see information theory entering?  

---

