0:04

In this sequence of videos we're going to discuss an important, if somewhat poorly

Â understood, approach to tackling NP complete problems namely local search.

Â Before I discuss the general principals of local search algorithms, I want to begin

Â with a concrete example that's going to be to the maximum cut problem.

Â 0:23

Some of you might remember that we studied the minimum cut problem in part

Â one of the course, in particular, Carver's randomized contraction algorithm.

Â That problem was defined as seeking out the cut of the graph that minimizes

Â the number of crossing edges.

Â The maximum cut problem, naturally enough,

Â we want the cut that maximizes the number of crossing edges.

Â 0:42

More precisely, we're given, as input, an undirected graph g.

Â And the responsibility of the algorithm is to output a cut that is a partition of

Â the vertices into two non-empty sets, A and B, that maximizes the number of

Â edges that have exactly one endpoint in each of the two groups of the partition.

Â 1:00

In the quiz on the next slide I'll give you an example to make sure that this

Â definition makes sense.

Â Before that just a couple of quick comments.

Â So first, sadly, unlike the minimum cut problem which we saw in part one is

Â computationally tractable, the maximum cut problem,

Â in general, is computationally intractable, it's NP-complete.

Â More precisely, the decision version of the question where you're given a graph

Â you want to know whether or not there exists a cut

Â that cuts at least a certain number of edges, that's an NP-complete problem.

Â There's no polynomial time algorithm for it unless P equals NP.

Â Like most NP-complete problems,

Â there are some computational tractable special cases.

Â For example the case of bipartite graphs.

Â 1:50

A slick way to solve this problem in linear time is to use

Â breadth-first search.

Â You just root the breadth-first search at a arbitrary vertex of the graph.

Â You draw for your breadth-first search tree.

Â You put the even layers as one of your groups A.

Â You take the odd layers and make it the other group B.

Â This will have no crossing edges, if and only if, the graph is bipartite.

Â 2:38

Specifically, take one group to the vertices w, n,

Â x, and take the group B to be the vertices u, v, y and z.

Â There are no edges internal to A, there are no edges internal to B.

Â Every edge has one endpoint in each.

Â 2:55

So while the max cut problem is computationally tractable in bipartite

Â graphs like this one using breadth-first search, it's NP-complete in general.

Â More over, breath-first search turns out to be not a very good heuristic for

Â approximating the maximum cut problem in general graphs.

Â We're going to have to turn to other techniques.

Â 3:22

Local search is a general heuristic design paradigm.

Â But I don't want to describe it in general until the following video,

Â after we've gone through this concrete example.

Â But at a higher level,

Â you should think of it that we're always maintaining a candidate cut.

Â And we just want to iteratively make it better and better via small,

Â that is local, modifications.

Â 3:42

To succinctly state the algorithm I'm going to need a little bit of notation.

Â So imagine that we have some undirected graph and

Â we're trying to approximate the maximum cut.

Â And suppose we have some current candidate cut A,B.

Â Some of the vertices are in A the rest are in B.

Â Now focus on some arbitrary vertex v, v can be an A or B I don't care.

Â There is some incident edges to this vertex v, in the graph on the right,

Â I've shown you a vertex v, it has degree five, five incident edges.

Â Now, some of these edges are crossing the cut, some of the edges are not.

Â So I'm going to use the notation c sub v (A,

Â B) to denote the number of v's incident edges that are crossing the cut.

Â And d sub v (A,

Â B) to denote the edges, the number of edges which are not crossing the cut.

Â So in the picture that I've drawn, c sub v would be equal to two,

Â d sub v would be equal to three.

Â 4:33

Here then is the local search algorithm for maximum cut.

Â In step one, we just begin with an arbitrary cut of the graph, so we just

Â somehow, I don't care how, put some of the vertices in A, some of the vertices in B.

Â 4:54

So what's a principled way to take a given cut and make it better?

Â Well, let's just focus on very simple modifications.

Â Let's suppose the only thing we're allowed to do is take a vertex from one of the two

Â groups say, from group A, and move it to group b.

Â For example, in the green network I've showed you on the right-hand

Â part of this slide, if we envision taking the vertex v and

Â moving it from A to B, we get a superior cut.

Â Why is that true?

Â Well here are the two ramifications of moving v from A to B.

Â So, first of all, the two edges incident to v that used to be crossing the cut,

Â they no longer cross the cut.

Â When we put v over on the right hand side the two edges who's

Â other end points are in B those edges get sucked in internally to B.

Â They are no longer crossing the cut.

Â On the other hand, the good news is, is that the three edges incident to v with

Â the other endpoint in A they used to be internal to the group A, but when we bring

Â v over to the right hand side to the group B, now those three edges cross the cut.

Â So we lost two edges from the cut but we gained three so

Â that's a net improvement of one more edge crossing the cut.

Â In general this argument shows that for any vertex so

Â that the number of edges incident to it that are not crossing the cut,

Â if that's bigger than the number which are crossing the cut incident to it,

Â Then switching sides with that vertex will improve the cut.

Â And the improvement is exactly the difference between the two quantities

Â d sub v and c sub v.

Â 6:19

If we find ourself with a cut such that there's no vertex switch

Â that improves the cut, that is if d sub v and (A, B) is at most c sub v of (A,

Â B) for every single vertex v.

Â Then we stop and we just return to the cut that we ended up with.

Â 6:35

We typically evaluate algorithms along two axes.

Â First of all, how good is their solution?

Â So, for example, is the algorithm always correct, or

Â at least approximately correct?

Â And secondly, what resources does it require?

Â So, for example, is the running time reasonable?

Â Now to be honest local search algorithms often perform poorly at least in

Â the worst case along both of these criteria.

Â This local search algorithm for

Â the maximum cut problem is interesting in that we can say non-trivial positive

Â things both about the solution quality and about its running time.

Â The running time bound follows easily from an observation that we made earlier.

Â Namely that every time we do an iteration of the while loop,

Â every time we switch a vertex from one side to the other,

Â the number of crossing edges goes up necessarily by at least one.

Â So I'm going to assume that the graph is simple, that there's no parallel edges.

Â In which case, there's at most n choose 2 edges in the graph, that means that this

Â while loop can only execute in total an n choose 2 or quadratic number of times.

Â It's easy to implement each iteration of the while loop quickly, so

Â that means this overall algorithm will terminate in polynomial time.

Â 7:40

Now this local search algorithm does not solve the maximum cut problem optimally.

Â It does not guarantee to return the maximum cut.

Â Indeed, that would be way to much to hope for

Â now that we know that it runs in polnomial time.

Â Remember the maximum cut problem is NP-complete.

Â However, interestingly,

Â this is a heuristic with a good worse case performance guarantee.

Â