1 00:00:04,057 --> 00:00:08,481 In this sequence of videos we're going to discuss an important, if somewhat poorly 2 00:00:08,481 --> 00:00:13,390 understood, approach to tackling NP complete problems namely local search. 3 00:00:13,390 --> 00:00:17,420 Before I discuss the general principals of local search algorithms, I want to begin 4 00:00:17,420 --> 00:00:20,640 with a concrete example that's going to be to the maximum cut problem. 5 00:00:23,750 --> 00:00:26,880 Some of you might remember that we studied the minimum cut problem in part 6 00:00:26,880 --> 00:00:30,610 one of the course, in particular, Carver's randomized contraction algorithm. 7 00:00:30,610 --> 00:00:33,610 That problem was defined as seeking out the cut of the graph that minimizes 8 00:00:33,610 --> 00:00:35,050 the number of crossing edges. 9 00:00:35,050 --> 00:00:37,130 The maximum cut problem, naturally enough, 10 00:00:37,130 --> 00:00:40,180 we want the cut that maximizes the number of crossing edges. 11 00:00:42,020 --> 00:00:45,250 More precisely, we're given, as input, an undirected graph g. 12 00:00:45,250 --> 00:00:49,840 And the responsibility of the algorithm is to output a cut that is a partition of 13 00:00:49,840 --> 00:00:54,460 the vertices into two non-empty sets, A and B, that maximizes the number of 14 00:00:54,460 --> 00:00:58,409 edges that have exactly one endpoint in each of the two groups of the partition. 15 00:01:00,040 --> 00:01:02,690 In the quiz on the next slide I'll give you an example to make sure that this 16 00:01:02,690 --> 00:01:04,130 definition makes sense. 17 00:01:04,130 --> 00:01:06,840 Before that just a couple of quick comments. 18 00:01:06,840 --> 00:01:10,940 So first, sadly, unlike the minimum cut problem which we saw in part one is 19 00:01:10,940 --> 00:01:13,690 computationally tractable, the maximum cut problem, 20 00:01:13,690 --> 00:01:17,350 in general, is computationally intractable, it's NP-complete. 21 00:01:17,350 --> 00:01:20,280 More precisely, the decision version of the question where you're given a graph 22 00:01:20,280 --> 00:01:22,980 you want to know whether or not there exists a cut 23 00:01:22,980 --> 00:01:26,690 that cuts at least a certain number of edges, that's an NP-complete problem. 24 00:01:26,690 --> 00:01:31,500 There's no polynomial time algorithm for it unless P equals NP. 25 00:01:31,500 --> 00:01:33,063 Like most NP-complete problems, 26 00:01:33,063 --> 00:01:35,660 there are some computational tractable special cases. 27 00:01:35,660 --> 00:01:38,030 For example the case of bipartite graphs. 28 00:01:40,360 --> 00:01:44,160 One definition of a bipartite graph is a graph in which there exists a cut, so 29 00:01:44,160 --> 00:01:46,280 that every single edge is crossing it. 30 00:01:46,280 --> 00:01:48,920 And then obviously, that would be the maximum cut of the graph. 31 00:01:50,730 --> 00:01:53,667 A slick way to solve this problem in linear time is to use 32 00:01:53,667 --> 00:01:54,885 breadth-first search. 33 00:01:54,885 --> 00:01:58,365 You just root the breadth-first search at a arbitrary vertex of the graph. 34 00:01:58,365 --> 00:01:59,825 You draw for your breadth-first search tree. 35 00:01:59,825 --> 00:02:02,585 You put the even layers as one of your groups A. 36 00:02:02,585 --> 00:02:05,765 You take the odd layers and make it the other group B. 37 00:02:05,765 --> 00:02:09,165 This will have no crossing edges, if and only if, the graph is bipartite. 38 00:02:13,050 --> 00:02:18,161 To make sure the definition of the maximum cut problem makes sense, 39 00:02:18,161 --> 00:02:22,745 what is the maximum cut in the following six-vertex graph? 40 00:02:26,568 --> 00:02:29,260 So the correct answer is c, 8. 41 00:02:29,260 --> 00:02:31,920 That's because the graph is bipartite. 42 00:02:31,920 --> 00:02:32,860 Only 8 edges and 43 00:02:32,860 --> 00:02:37,280 there is indeed a cut in which every single one of those edges crosses it. 44 00:02:38,360 --> 00:02:41,983 Specifically, take one group to the vertices w, n, 45 00:02:41,983 --> 00:02:45,783 x, and take the group B to be the vertices u, v, y and z. 46 00:02:45,783 --> 00:02:49,850 There are no edges internal to A, there are no edges internal to B. 47 00:02:49,850 --> 00:02:52,488 Every edge has one endpoint in each. 48 00:02:55,661 --> 00:02:58,628 So while the max cut problem is computationally tractable in bipartite 49 00:02:58,628 --> 00:03:02,408 graphs like this one using breadth-first search, it's NP-complete in general. 50 00:03:02,408 --> 00:03:06,270 More over, breath-first search turns out to be not a very good heuristic for 51 00:03:06,270 --> 00:03:08,962 approximating the maximum cut problem in general graphs. 52 00:03:08,962 --> 00:03:11,549 We're going to have to turn to other techniques. 53 00:03:13,150 --> 00:03:16,610 There's a number of interesting heuristics for the maximum cut problem. 54 00:03:16,610 --> 00:03:21,030 But I want to use the problem here to showcase the technique of local search. 55 00:03:22,760 --> 00:03:25,855 Local search is a general heuristic design paradigm. 56 00:03:25,855 --> 00:03:29,355 But I don't want to describe it in general until the following video, 57 00:03:29,355 --> 00:03:31,935 after we've gone through this concrete example. 58 00:03:31,935 --> 00:03:32,685 But at a higher level, 59 00:03:32,685 --> 00:03:35,395 you should think of it that we're always maintaining a candidate cut. 60 00:03:35,395 --> 00:03:39,445 And we just want to iteratively make it better and better via small, 61 00:03:39,445 --> 00:03:41,305 that is local, modifications. 62 00:03:42,560 --> 00:03:46,510 To succinctly state the algorithm I'm going to need a little bit of notation. 63 00:03:46,510 --> 00:03:48,415 So imagine that we have some undirected graph and 64 00:03:48,415 --> 00:03:50,690 we're trying to approximate the maximum cut. 65 00:03:50,690 --> 00:03:53,129 And suppose we have some current candidate cut A,B. 66 00:03:53,129 --> 00:03:56,280 Some of the vertices are in A the rest are in B. 67 00:03:56,280 --> 00:04:01,293 Now focus on some arbitrary vertex v, v can be an A or B I don't care. 68 00:04:01,293 --> 00:04:05,319 There is some incident edges to this vertex v, in the graph on the right, 69 00:04:05,319 --> 00:04:09,890 I've shown you a vertex v, it has degree five, five incident edges. 70 00:04:09,890 --> 00:04:14,090 Now, some of these edges are crossing the cut, some of the edges are not. 71 00:04:14,090 --> 00:04:16,721 So I'm going to use the notation c sub v (A, 72 00:04:16,721 --> 00:04:20,920 B) to denote the number of v's incident edges that are crossing the cut. 73 00:04:20,920 --> 00:04:22,056 And d sub v (A, 74 00:04:22,056 --> 00:04:25,990 B) to denote the edges, the number of edges which are not crossing the cut. 75 00:04:25,990 --> 00:04:30,200 So in the picture that I've drawn, c sub v would be equal to two, 76 00:04:30,200 --> 00:04:31,740 d sub v would be equal to three. 77 00:04:33,890 --> 00:04:36,910 Here then is the local search algorithm for maximum cut. 78 00:04:36,910 --> 00:04:40,970 In step one, we just begin with an arbitrary cut of the graph, so we just 79 00:04:40,970 --> 00:04:44,700 somehow, I don't care how, put some of the vertices in A, some of the vertices in B. 80 00:04:46,410 --> 00:04:49,700 Now, we just iteratively try to make the cut that we're working with better 81 00:04:49,700 --> 00:04:52,120 until we don't see any easy way to improve it further. 82 00:04:54,020 --> 00:04:57,430 So what's a principled way to take a given cut and make it better? 83 00:04:57,430 --> 00:05:00,460 Well, let's just focus on very simple modifications. 84 00:05:00,460 --> 00:05:03,690 Let's suppose the only thing we're allowed to do is take a vertex from one of the two 85 00:05:03,690 --> 00:05:07,710 groups say, from group A, and move it to group b. 86 00:05:07,710 --> 00:05:10,840 For example, in the green network I've showed you on the right-hand 87 00:05:10,840 --> 00:05:14,300 part of this slide, if we envision taking the vertex v and 88 00:05:14,300 --> 00:05:19,230 moving it from A to B, we get a superior cut. 89 00:05:19,230 --> 00:05:20,380 Why is that true? 90 00:05:20,380 --> 00:05:23,700 Well here are the two ramifications of moving v from A to B. 91 00:05:23,700 --> 00:05:27,970 So, first of all, the two edges incident to v that used to be crossing the cut, 92 00:05:27,970 --> 00:05:29,480 they no longer cross the cut. 93 00:05:29,480 --> 00:05:32,990 When we put v over on the right hand side the two edges who's 94 00:05:32,990 --> 00:05:36,750 other end points are in B those edges get sucked in internally to B. 95 00:05:36,750 --> 00:05:38,800 They are no longer crossing the cut. 96 00:05:38,800 --> 00:05:42,690 On the other hand, the good news is, is that the three edges incident to v with 97 00:05:42,690 --> 00:05:46,960 the other endpoint in A they used to be internal to the group A, but when we bring 98 00:05:46,960 --> 00:05:52,150 v over to the right hand side to the group B, now those three edges cross the cut. 99 00:05:52,150 --> 00:05:55,470 So we lost two edges from the cut but we gained three so 100 00:05:55,470 --> 00:05:59,370 that's a net improvement of one more edge crossing the cut. 101 00:05:59,370 --> 00:06:02,410 In general this argument shows that for any vertex so 102 00:06:02,410 --> 00:06:06,250 that the number of edges incident to it that are not crossing the cut, 103 00:06:06,250 --> 00:06:09,820 if that's bigger than the number which are crossing the cut incident to it, 104 00:06:09,820 --> 00:06:13,500 Then switching sides with that vertex will improve the cut. 105 00:06:13,500 --> 00:06:16,820 And the improvement is exactly the difference between the two quantities 106 00:06:16,820 --> 00:06:18,220 d sub v and c sub v. 107 00:06:19,990 --> 00:06:23,970 If we find ourself with a cut such that there's no vertex switch 108 00:06:23,970 --> 00:06:28,771 that improves the cut, that is if d sub v and (A, B) is at most c sub v of (A, 109 00:06:28,771 --> 00:06:30,120 B) for every single vertex v. 110 00:06:30,120 --> 00:06:33,809 Then we stop and we just return to the cut that we ended up with. 111 00:06:35,120 --> 00:06:38,000 We typically evaluate algorithms along two axes. 112 00:06:38,000 --> 00:06:39,753 First of all, how good is their solution? 113 00:06:39,753 --> 00:06:42,030 So, for example, is the algorithm always correct, or 114 00:06:42,030 --> 00:06:44,250 at least approximately correct? 115 00:06:44,250 --> 00:06:46,560 And secondly, what resources does it require? 116 00:06:46,560 --> 00:06:48,484 So, for example, is the running time reasonable? 117 00:06:48,484 --> 00:06:52,559 Now to be honest local search algorithms often perform poorly at least in 118 00:06:52,559 --> 00:06:55,630 the worst case along both of these criteria. 119 00:06:55,630 --> 00:06:56,750 This local search algorithm for 120 00:06:56,750 --> 00:07:00,212 the maximum cut problem is interesting in that we can say non-trivial positive 121 00:07:00,212 --> 00:07:03,516 things both about the solution quality and about its running time. 122 00:07:03,516 --> 00:07:07,200 The running time bound follows easily from an observation that we made earlier. 123 00:07:07,200 --> 00:07:09,595 Namely that every time we do an iteration of the while loop, 124 00:07:09,595 --> 00:07:12,270 every time we switch a vertex from one side to the other, 125 00:07:12,270 --> 00:07:16,170 the number of crossing edges goes up necessarily by at least one. 126 00:07:16,170 --> 00:07:18,920 So I'm going to assume that the graph is simple, that there's no parallel edges. 127 00:07:18,920 --> 00:07:22,910 In which case, there's at most n choose 2 edges in the graph, that means that this 128 00:07:22,910 --> 00:07:29,300 while loop can only execute in total an n choose 2 or quadratic number of times. 129 00:07:29,300 --> 00:07:32,559 It's easy to implement each iteration of the while loop quickly, so 130 00:07:32,559 --> 00:07:35,945 that means this overall algorithm will terminate in polynomial time. 131 00:07:40,406 --> 00:07:44,890 Now this local search algorithm does not solve the maximum cut problem optimally. 132 00:07:44,890 --> 00:07:48,060 It does not guarantee to return the maximum cut. 133 00:07:48,060 --> 00:07:49,600 Indeed, that would be way to much to hope for 134 00:07:49,600 --> 00:07:51,700 now that we know that it runs in polnomial time. 135 00:07:51,700 --> 00:07:55,070 Remember the maximum cut problem is NP-complete. 136 00:07:55,070 --> 00:07:56,654 However, interestingly, 137 00:07:56,654 --> 00:08:00,352 this is a heuristic with a good worse case performance guarantee. 138 00:08:01,989 --> 00:08:05,423 Precisely the outcome of this local search algorithm is 139 00:08:05,423 --> 00:08:10,097 guaranteed to be a cut in which the number of crossing edges is at least half, 140 00:08:10,097 --> 00:08:12,670 at least 50% of the maximum possible. 141 00:08:14,440 --> 00:08:16,130 In fact, something stronger is true. 142 00:08:16,130 --> 00:08:20,040 It's even guaranteed to be at least 50% of all of the edges of the graph. 143 00:08:20,040 --> 00:08:23,883 Which of course is an upper bound on the maximum number of edges crossing some cut.