[MUSIC] Now let us start the serious work. How do we design an LP relaxation for Maxcut? First we start with an integer programming relaxation. How do we represent Maxcut? Let's see. The goal is to do better than the factor of two. Remember that the value of the output is the sum of every edge, of the width of the edge times one if ij crosses the cut and zero if not. One or zero. What does this suggest? Naturally it suggests to have one variable xij for every edge ij. That will be equal to one if the edge crosses the cut and zero otherwise. And then the objective will be to maximize this sum over every edge of wijxij. But the big question is how do we represent cuts? What if we want to have an exact model for max cut? What properties do cuts have? Given a vector xe, indexed by all the of the graph, when does there exist a partition of the graph vertices into two sets, S and V-S associated to these variables x sub e? The idea is, it's actually simpler to do if we define the variable x sub i j not for each edge, but for each vertex pair. This way it will have more information in our vector x, and it will be easier to decide weather i exist in [INAUDIBLE] partition. Okay. So, now let's say we have one variable xij for each vertex pair in the graph. What are the properties of the cut? Here is one property. Well first of course there's implicit symmetry. I won't even talk about it. xij = xji because the graph is, that's just the way it is. And the graph is undirected and everything is undirected. Everything is symmetric. Let's sweep this under the carpet. Unimportant detail for our purpose. I claim that. This vector x satisfies the triangular inequality. I claim that for every three vertices, ijk, xij is less than xik + xkj. Why? Why? Well, xij is either zero or one. If xij is zero, we're good. This inequality will be satisfied. If xij is one, what does it mean? It means that edge, that the vertex pair j crosses the cut. It means that i is on one side, j is on the other side. Then what about k? k must be with i or with j, but not both. For example, k is with i. In that case, xik, 0, they're on the same side. But xkj is 1. They're on different sides of the cut. Indeed, k cannot be on the same side as both i and j. It has to be separated from at least one of them. Therefore, of the two terms on the right, one of them must be one, and will have one less than or equal to 0 + 1. Good. This inequality is true for every vector x associated to a cut. So we can put this in our integer program as a constraint. For every triplet of vertices, i, j, and k, xij is less than or equal to xik + xkj. Next. I claim that xij + xjk + xki is at most 2. Why? Because we have a cut of the graph into two parts, not three parts, but two parts. So, regardless of the induced partition on the three vertices ijk, regardless of how split they are, they cannot all three of them be on three different sides of the cut, because a cut has only two sides. So, for example, if ik are on one side, j is on the other side, then the cut crosses two of the three vertex pairs. And that's the maximum. Therefore these three variables one of them at least must be zero. And therefore this sum is at most two. That's another linear inequality that is satisfied by every cut. Put those together. xij less than xjk + xkj, xij + xkj + xki at most 2. xij = 0 or to 1. This is a representation of cuts. Whenever you have a vector x that satisfies this, there exists a cut S. Such that xij = 1 if and only if the pair r j crosses the cut. So there exists an associated cut and vice versa. For every cut, there's an associated vector x that satisfies these properties. This implication is clear, we just went through it. The other implication needs a proof, do these inequalities suffice to represent cuts? Let's see. Here is the proof. We have x, an integer vector that satisfies these constraints. Let us build a cut. All right. We have to decide for each vertex, which one goes in S, which one goes in V- S. Vertex one, put it in S. Vertices such as x1i = 0, every such vertex i. It is that i is on the same size as vertex one, so we also put it in S. And that's it. This is the only possible cut associated to vector x. Except of course for switching S and V- S. So let's see. Is this correct? Does this work? If you consider this cut, is it true that the associated vector corresponds to x? Do we have the correct x? All the inequalities are valid. Let's see. First consider xij, where i is in S and j is not in S. It crosses. We said x1i is zero. And of course, x1j is one since j is not in S. By definition of S, S contains all the vertices that have x1i = 0. j is not in S, therefore x1j must be one. Okay. Now by the triangular inequality, x1j is less than x1i + xij. x1j = 1 since j is not in S. x1i is 0 since i is in S. And now both of these are by definition of S and now from this we infer xij is at least one. In other words, xii must be equal to one. So from the definition of S and the triangle equality, we infer that, if i is in S and j not in S then xij = 1. So it does correspond to crossing the cut, as it should. The algorithm is symmetrical when i is not in S and j in S. Now consider xij where i and j are both elements of S. Hopefully, xij is equal to 0. Hopefully. So let's see, what do we know? By the triangular inequality again, xij is less than xi1 + x1j, at most that. xi1, since i is in S, by definition of S, xi1 = 0. x1j, since j is in S, by definition of S, x1j is 0, therefore xij is at most 0, so it has to be equal to 0. xij = 0, as it should. This edge, this vertex pair is not crossing the cut. Finally, last case, xij where neither i nor j are in S. Then we turn to our other constraint. The sum of xij, x1i, x1j, must be at most 2. That's the inequality for k equal to 1. Now, what can we say? i is not in s, therefore, by definition of S, x1i must be equal to 1. Similarly x1j must be equal to one, one plus one, two, plus xij is at most two. xij must be zero. There's no other possibility as it should. Since these vertices are on the other side, the pair does not cross the cut. So with this, we have proved that S satisfies exactly, corresponds exactly to the information given by xij. And so what we have is a correct integer programming model for Maxcut. Then, what do we do with it? We design a linear programming relaxation. How do we design this relaxation? As usual, we get rid of the integer constraint. And we replace it, by the constraint that xij must be between 0 and 1. So this is our linear programming relaxation for Maxcut. Symmetric variables, xij = xji for every vertex pair, i, j. Maximize the weighted sum of xijs for i, j, and h such that xij satisfies the triangular inequality and triple, the sum of our three variables is at most two. And they're all between 0 and 1. This is the that one might hope to use either by doing rounding or a logarithm or something to try to get a better than two approximation. In the next part, we will see that this does not work.