[MUSIC] In this chapter we will study the famous Maxcut problem and present the famous algorithm due to Michelle Gomez and David Williamson from the mid-1990s. Perhaps the most famous approximation algorithm that there is. Okay, so let's talk about the Maxcut problem. What is the definition of this problem? Given, a graph, with non-negative edge weights. A graph with edge weights, find a partition of the vertices into two subsets. So as to maximize the weight of the edges going across the cut. The total weight of the edges going from the left to the right side, that's the Maxcut problem. Where does it come from? It comes from, for example, it's relevant to statistical physics. And it also has many variants that come up in applications. Let's look at this on some example, simple example. Take the grid, the four-by-four grid, 16 vertices. Imagine every edge has weight equal to 1. What is the value of Maxcut? We have to try every cut to see what the maximum is, that's the naive way of doing it. Let's see, let's take this cut, separating this vertex from everything else. This cut crosses two edges, value 2. Let's take a different cut. The vertical cut separating the left side vertices from the right side vertices. Value one, two, three, four edges across. Four edges go across the cut, the value of this cut is 4, it is better than the previous one. How about the partition into empty set on one side and the entire set on the other side? No edge crosses, value zero. How about this cut? This red cut here, I'm not going to trace it because it's too hard. But you can check that it crosses every single edge. Every single edge is crossed. And therefore, Its value is 24. All the edges are cut by this partition. And that is the best possible. In this case, the graph is barred by tight, that helps. So, let's see, here are some properties that are not imposed in the definition of Maxcut. There is no particular pair {s,t} of vertices that must be separated by the cut. And the cut does not have to be 50-50. It does not have to be a balanced cut. If you look at this, about two-thirds of the graph is on the left and the one-third is on the right. That is allowed. No constraint on the cardinalities of the sides, no constraint on where specific vertices go. It's just any cut among the two to the end possible cuts. For each cut, look at the weight of edges crossing, take the maximum. That's the Maxcut problem. Probably, it reminds you of something you have seen earlier in some algorithms cross Mincut. Let's take a quick look at the similarities and differences between them. In both cases we're given a graph with non-negative edge weights. In addition, for Mincut we have two special vertices, s and t. That's what sometimes causes the confusion. In both cases, the goal is to find a partition of the vertices into two sets. But in addition, in the case of Mincut, we want to separate s from t. In case of Maxcut, we want to maximum the weight of the edges across the cut. In the case of Mincut, we want to minimize the weight of edges across the cut. You can see here, this cut separates s from t, and it has very few edges crossing and they are very light compared to that cut. Well what's interesting is that the Mincut problem can be solved in polynomial time. It's related to the max flow problem, but the Maxcut problem is NP-hard. Who proved it's NP-hard? Take a guess. Karp, of course, of course. He's the one who took these initial fundamental problems and proved them all NP-hard. So, we have our basic fundamental problem from graph theory, graph optimization. We know it's NP-hard, and now we want to try to design an approximation algorithm for it. And this will lead us to a new technique for the design of algorithms in approximation.
