[MUSIC] In this section, I will show how to round the solution of a quadratic program. So we have our quadratic relaxation for Maxcut where every vertex has an associated unit length vector. And we have solved it using a mysterious black box algorithm called the ellipsoid algorithm. Now we have our vectors, we need to figure out how to deduce a partition of the vertices of the graph into two parts, that is given the vector Vi, a unit vector. We want to deduce the value of Xi of among two possibilities, and here it is easier to think of the two possibilities as being -1 or 1. So we have a vector on the sphere in high dimension, and we want to decide whether to associate to it the value -1 or the value 1. Once we have done that, as a result of the rounding, then we will output the resulting partition, and the value will be the weighted sum of 1- XiXj / 2. What we know is that because the quadratic relaxation is a relaxation, opt is at most, the weighted sum 1- Vi.Vj / 2. So our algorithm will be good if these two values are close to one another. So we wish to round our quadratic program so that 1- XiXj / 2 is similar to 1- Vi.Vj / 2. How do we do this? If you have two vectors, Vi and Vj, that are lined up, if they are in the same position, then Vi.Vj equals 1. They are unit vectors. And then, this equals 0. In that case, to have the same value here, what we want is Xi = Xj. On the other hand, if the two vectors are opposites like this, then 1- Vi.Vj / 2 equals 1, and then what we want is we want the same thing to hold for Xi and Xj. We want xi to be equal to -xj, so that this quantity is also equal to 1. And if the vectors are everything in between, this is vi, vj could be more or less lined up, more or less. Then we cannot have exactly the same thing as this, because this quantity will be something between -101. So we want something that is close to it as possible. So what we want is these two vectors to give us Xi, Xj, that tend to be the same if the vectors tend to be lined up and tend to be different if the vectors tend to be opposite. We want far apart vectors to map to different values of Xi, Xj, close by vectors to map to similar values of Xi and Xj. So how do we do it? The idea is, since here there's no clear way to do it, again, when we don't know what to do, we use randomness. We get to use randomized rounding. Randomized rounding, right here, the idea is we're going to split the sphere, the unit sphere in half using a random hyperplane. Pick a random hyperplane H through the origin. It randomly splits the sphere into two parts. Above H, every vector that is above it goes to 1, every vector that is below it goes to -1. Then what happens? Look at this, here's my hyperplane H. If the two vectors are aligned up, Vi, Vj, then, either they're both above or both below. So either they will both map to 1 or both map to -1 and therefore, we will have Xi = Xj as we desire. Similarly, if the two vectors are opposite, then regardless of how our hyperplane is oriented, the two vectors will fall on different sides of the hyperplane. And therefore, we will have one of the two values at 1 and the other at -1 as desired. And then if the two factors are somewhere in between, then the closer they are together, the less likely it is that the hyperplane will fall in between, and the more likely it is that Xi and Xj will be equal. So that has a right feel. So that's the algorithm. First, we solve the quadratic vector program, the relaxation for Maxcut, this gives us one unit length vector for each vertex, then we pick one random hyperplane through the origin. Every vector that is above the corresponding vertex maps to 1, every vector that is below the corresponding vector maps to -1, that defines the partition of our vertices of the two sets, and that's the output. Only one question remains, how does one pick a random hyperplane? Here is the way to do it. Pick a point, uniformly at random on the unit sphere. This point defines a vector, a unit length vector. Take the normal hyperplane through the origin, that's a hyperplane used to separate the vectors into two sets. Okay, only one question remains still, how do we pick a point uniformly at random on the unit sphere in high dimension? In two dimensions, it's easy, the radius is 1, the angle is uniform between 0 and 2pi. In high dimensions, two ways to do it. Either we say, we define the vector by defining Xi as an independent, random variable drawn from the normal distribution with mean 0 and standard deviation 1. And then, we define the unit vector as X over the norm of X. That's how we can define this vector. Or we can use spherical coordinators. Say the radius is 1, and all the angles are independent uniform. So either way, both of these things are valid techniques to pick a point on the unit sphere. And so that defines our approximation algorithm for Maxcut.
