1 00:00:00,012 --> 00:00:04,671 A greedy heuristic for the knapsack problem is pretty good, but let's work a 2 00:00:04,671 --> 00:00:09,194 little harder and do quite a bit better. We're going to accomplish a quite 3 00:00:09,194 --> 00:00:12,844 ambitious goal. The knapsack problem, being NP-complete, 4 00:00:12,844 --> 00:00:17,163 is not we expect going to admit an exact polynomial time algorithm. 5 00:00:17,163 --> 00:00:21,518 Let's shoot for the next best thing, arbitrarily close approximation. 6 00:00:21,518 --> 00:00:26,618 That is, let's accept from a user error parameter epsilon, and, return the 7 00:00:26,618 --> 00:00:31,676 solution whose value is guaranteed to be at least ibe minus epsilon times that of 8 00:00:31,676 --> 00:00:36,202 an optimal knapsack solution. So, a client who wants to be guaranteed 9 00:00:36,202 --> 00:00:41,138 that this heuristic outputs a solution with a 99% of optimal just has to set 10 00:00:41,138 --> 00:00:44,897 epsilon to be 0.01. If this sounds a little too good to be 11 00:00:44,897 --> 00:00:48,652 true, there is a catch. The running time is going to increase as 12 00:00:48,652 --> 00:00:51,152 we take epsilon to be smaller and smaller. 13 00:00:51,152 --> 00:00:55,482 But what this algorithm exports to the client is an accuracy running time 14 00:00:55,482 --> 00:00:58,462 trade-off. That is, it exports via this parameter 15 00:00:58,462 --> 00:01:01,817 epsilon a knob that the user can turn wherever they want. 16 00:01:01,817 --> 00:01:06,337 If you want more accuracy and are willing to wait a little bit longer, you set 17 00:01:06,337 --> 00:01:10,767 epsilon to be epsilon to be smaller. If you want something really fast and 18 00:01:10,767 --> 00:01:14,521 you're okay with a bit of inaccuracy, you take espsilon to be bigger. 19 00:01:14,521 --> 00:01:17,669 And, this is as good as it gets, for Np-complete problems. 20 00:01:17,669 --> 00:01:21,870 Assuming P is not equal to NP, there's no way to solve it exactly in polynomial 21 00:01:21,870 --> 00:01:25,692 time, the next best thing you can have, hope for, is arbitrarily close 22 00:01:25,692 --> 00:01:29,980 approximation, in polynomial time. That is what we will get for the napsack 23 00:01:29,980 --> 00:01:32,925 problem using a dynamic programming base heuristic. 24 00:01:32,925 --> 00:01:36,874 Sadly, the knapsack problem is the exception that proves the rule. Most 25 00:01:36,874 --> 00:01:40,956 NP-complete problems, it is believed you cannot get an arbitrarily close 26 00:01:40,956 --> 00:01:44,109 approximation. One concrete example is the vertex cover 27 00:01:44,109 --> 00:01:46,602 problem, we discussed exact, expnential time 28 00:01:46,602 --> 00:01:50,831 algorithms for vertex cover in a seperate video and we've been talking about 29 00:01:50,831 --> 00:01:55,460 polynominal time heuristics for vertex cover, and there are some good ones. You 30 00:01:55,460 --> 00:02:00,068 can get within a factor two of an optimum vertex cover in polynomial time, but, it 31 00:02:00,068 --> 00:02:04,715 is believed you cannot get arbitrarily close approximation of the optimal vertex 32 00:02:04,715 --> 00:02:09,021 cover in polynomial time. In fact, if you came up with such an algorithm, that 33 00:02:09,021 --> 00:02:12,673 would imply p equals NP. While there are some other problems out 34 00:02:12,673 --> 00:02:16,556 there like knapsack that admit arbitrarily close approximation, there's 35 00:02:16,556 --> 00:02:20,521 many more out there which are like vertex cover where, assuming p not equal to NP, 36 00:02:20,521 --> 00:02:24,740 it is not possible to get arbitrarily close approximation in polynomial time. 37 00:02:24,740 --> 00:02:28,714 But this is an algorithms class, we should stay positive and focus on what 38 00:02:28,714 --> 00:02:31,551 you can do. So let's move on to the arbitrarily close 39 00:02:31,551 --> 00:02:35,715 approximation for knapsack. So the high-level idea is both very cool 40 00:02:35,715 --> 00:02:39,352 and also very natural. What we're going to do is we're going to 41 00:02:39,352 --> 00:02:44,033 take the knapsack instance that we're given, so items that have values and 42 00:02:44,033 --> 00:02:48,451 weights, and some kapsack capacity. And we're going to massage it a little 43 00:02:48,451 --> 00:02:51,165 bit, not too much, just a little bit but we 44 00:02:51,165 --> 00:02:56,028 want to put it squarely in one of our computationally tractable special cases, 45 00:02:56,028 --> 00:02:59,101 and then, we're going to solve this transformed version of the original 46 00:02:59,101 --> 00:03:00,971 input. Now, because we're not solving the 47 00:03:00,971 --> 00:03:03,978 problem that we were given, we're not going to get the right answer. 48 00:03:03,978 --> 00:03:07,270 But as long as we didn't transform it too much, we can hope that the optimal 49 00:03:07,270 --> 00:03:10,885 solution to the transformed problem is a pretty good approximation of the original 50 00:03:10,885 --> 00:03:15,357 problem that we were give. Well, what's a computationally tractable 51 00:03:15,357 --> 00:03:19,672 special case of the knapsack problem? To date, we do know one, but we only know 52 00:03:19,672 --> 00:03:23,867 one so far, which is if we assume that the sizes of the items in the knapsack 53 00:03:23,867 --> 00:03:28,106 capactiy are integers, we can go back to our dynamic programing solution for the 54 00:03:28,106 --> 00:03:32,293 knapsack problem which runs in time, n, the number of items time capital W, the 55 00:03:32,293 --> 00:03:35,272 knapsack capacity. So if it were the case of the knapsack 56 00:03:35,272 --> 00:03:39,010 capacity W wasn't too big, if for example, it was polynomial and the number 57 00:03:39,010 --> 00:03:44,981 of items, n, then this dynamic programing algorithm would run in polynomial time. 58 00:03:44,981 --> 00:03:52,005 For technical reasons, which I'll say a little bit more about later, this 59 00:03:52,005 --> 00:03:59,499 computationally tractable special case is not well-suited for deployment in a 60 00:03:59,499 --> 00:04:06,205 dynamic programming heuristic. Instead, we're going to want to develop a 61 00:04:06,205 --> 00:04:11,083 second similar but different computationally tractable special case. 62 00:04:11,083 --> 00:04:15,520 The second special case is when the sizes and the knapsack capacity can be 63 00:04:15,520 --> 00:04:20,232 arbitrary, but where the item values are integers that are not too big. This 64 00:04:20,232 --> 00:04:25,562 assumption can also be exploited by a dynamic programing algorithm. As we'll 65 00:04:25,562 --> 00:04:30,174 show in a separate video, there is a different dynamic programming 66 00:04:30,174 --> 00:04:35,529 algorithm for the knapsack problem, whose running time is N squared times the 67 00:04:35,529 --> 00:04:38,672 largest item value, N squared times Vmax. 68 00:04:38,672 --> 00:04:43,596 So from this second dynamic programming algorithm, we can extract a second 69 00:04:43,596 --> 00:04:47,909 computationally tractable special case of the knapsack problem. 70 00:04:47,909 --> 00:04:52,835 Namely if all of the item values are small integers, say a polynomial in the 71 00:04:52,835 --> 00:04:58,028 number of items n, then this dynamic programming algorithm already gives us a 72 00:04:58,028 --> 00:05:01,930 polynomial time algorithm for instances of that form. 73 00:05:01,930 --> 00:05:06,947 Armed with the second computationally tractable special case, we can now return 74 00:05:06,947 --> 00:05:11,223 to the high-level idea at the beginning of this slide and execute it. 75 00:05:11,223 --> 00:05:14,719 Here's how we do it. Our knapsack algorithm is given some 76 00:05:14,719 --> 00:05:18,623 knapsack instance, the item values need not be small integers. 77 00:05:18,623 --> 00:05:23,400 Now we massage the instance a little bit. We transform it, so that it becomes an 78 00:05:23,400 --> 00:05:26,735 instance that we know how to solve in polynomial time. 79 00:05:26,735 --> 00:05:30,835 How do we do that? We force the item values to be small integers. 80 00:05:30,835 --> 00:05:34,713 How do you take arbitrary numbers and make sure that they're small numbers? 81 00:05:34,713 --> 00:05:38,697 Well, the first thing to try is drop the low order bits and that's essentially 82 00:05:38,697 --> 00:05:41,492 what we're going to do. Our algorithm then, solves this 83 00:05:41,492 --> 00:05:45,513 transformed instance, by construction, the instance has small item value so we 84 00:05:45,513 --> 00:05:49,590 can solve it in polynomial time using our second dynamic programing algorithm. 85 00:05:49,590 --> 00:05:53,082 Now, we're probably not going to get an optimal solution to the original 86 00:05:53,082 --> 00:05:56,022 instance. After all, we solved the wrong instance. 87 00:05:56,022 --> 00:05:59,688 Unless we transform the values before invoking our dynamic programming 88 00:05:59,688 --> 00:06:02,334 algorithm. But, the hope, and this is just a hope, 89 00:06:02,334 --> 00:06:06,262 this is definitely going to require a proof. The hope is that we didn't loose 90 00:06:06,262 --> 00:06:09,586 too much information just by throwing out some lower order bits. 91 00:06:09,586 --> 00:06:13,458 So, by virtue of computing a solution which is 100% optimal, for the almost 92 00:06:13,458 --> 00:06:17,392 correct problem, maybe that solution is also almost optiomal for the fully 93 00:06:17,392 --> 00:06:22,482 correct correct problem. So here is the algorithm in full detail. 94 00:06:22,482 --> 00:06:27,167 It really only has two steps. Fist, we do the transformation. 95 00:06:27,167 --> 00:06:30,732 We round the item values to the small integers, 96 00:06:30,732 --> 00:06:36,447 then we invoke the second dynamic programming algorithm on the transformed 97 00:06:36,447 --> 00:06:40,304 instance. Precisely, here is how we round each item 98 00:06:40,304 --> 00:06:44,157 value v sub i. To begin, we decrease vi to the nearest 99 00:06:44,157 --> 00:06:48,573 multiple of a parameter m. I'm going to leave this parameter m 100 00:06:48,573 --> 00:06:54,417 unspecified at the moment and therefore this algorithm will be undetermined. 101 00:06:54,417 --> 00:06:59,775 Once we start analyzing the algorithm, we'll see what the parameter m has to be 102 00:06:59,775 --> 00:07:03,200 as a function of epsilon. So don't forget that epsilon is the 103 00:07:03,200 --> 00:07:05,669 accuracy parameter supplied by our client. 104 00:07:05,669 --> 00:07:09,541 If the client sets a given value of epsilon, what it means is that our 105 00:07:09,541 --> 00:07:13,772 responsibility is to output a feasible solution with value at least one minus 106 00:07:13,772 --> 00:07:16,291 epsilon times that of an optimal solution. 107 00:07:16,291 --> 00:07:20,462 So the smaller the epsilon, the more accurate our algorithm needs to be. 108 00:07:20,462 --> 00:07:24,813 When we round an item value vi down to the nearest multiple of m, we're 109 00:07:24,813 --> 00:07:28,212 decreasing it by an amount somewhere between 0 and m. 110 00:07:28,212 --> 00:07:32,162 If vi was already a multiple of m, we don't decrease it at all. 111 00:07:32,162 --> 00:07:36,492 If vi was just below a multiple of m, then we wind up decreasing it by 112 00:07:36,492 --> 00:07:39,894 essentially m. Therefore, the bigger the m, the more 113 00:07:39,894 --> 00:07:44,733 information we're throwing out about our instance and the less we should expect 114 00:07:44,733 --> 00:07:48,115 our accuracy. That is, the smaller value of epsilon the 115 00:07:48,115 --> 00:07:53,004 more accuracy demanded by our client, the smaller we're going to have to take our 116 00:07:53,004 --> 00:07:55,758 value of m. Now, once we've made everything a 117 00:07:55,758 --> 00:07:58,445 multiple of m, we may as well just scale down, 118 00:07:58,445 --> 00:08:02,702 we may as well divide everything by m, we're going to get integers. 119 00:08:02,702 --> 00:08:08,158 The integers that we get after rounding down to the nearest multiple of m and 120 00:08:08,158 --> 00:08:11,801 then dividing by m are going to be called the V hats. 121 00:08:11,801 --> 00:08:17,621 An alternative succinct way to describe the V hats is V hat i is by definition, 122 00:08:17,621 --> 00:08:21,094 Vi/m rounded down. And so these funny brackets in blue on 123 00:08:21,094 --> 00:08:24,283 the right, that's called the floor operator, 124 00:08:24,283 --> 00:08:29,728 that takes in a real number and returns the biggest integer that's less than or 125 00:08:29,728 --> 00:08:33,127 equal to the input. Thus, what is the transformation? In 126 00:08:33,127 --> 00:08:37,880 effect, we take the item values that were given, we divide them by this parameter m 127 00:08:37,880 --> 00:08:42,037 and then we also round down just to make sure we're dealing with integers. 128 00:08:42,037 --> 00:08:46,665 Step 2 of our heuristic is to just invoke the second dynamic programming algorithm 129 00:08:46,665 --> 00:08:49,134 to solve exactly the transformed instance. 130 00:08:49,134 --> 00:08:53,849 That is, we feed into that second dynamic programming algorithm, the instance with 131 00:08:53,849 --> 00:08:58,366 N items, the sizes are exactly the same as in the knapsack instance we were given 132 00:08:58,366 --> 00:09:01,328 originally. The knapsack capacity, capital W, is 133 00:09:01,328 --> 00:09:05,201 exactly the same we were given originally, but we feed in the values, V 134 00:09:05,201 --> 00:09:08,769 hat one through V hat n. That is, we solve it with respect to the 135 00:09:08,769 --> 00:09:12,476 transformed values, not with respect to the original values, 136 00:09:12,476 --> 00:09:15,299 the Vi's. Let's make two quick observations before 137 00:09:15,299 --> 00:09:19,484 we conclude. So first of all, remember the dynamic programming algorithm, the 138 00:09:19,484 --> 00:09:23,635 second one for knapsack, the running time is n squared times the largest item 139 00:09:23,635 --> 00:09:27,829 value, and of course, here we're running the dynamic programming algorithm with 140 00:09:27,829 --> 00:09:32,451 these transformed item values the V hats. So therefore, if the V hat are big, then 141 00:09:32,451 --> 00:09:35,668 this running time is slow, if the V hats are small, then this 142 00:09:35,668 --> 00:09:39,929 running time is going to be reasonable. Now, let's remember the definition of the 143 00:09:39,929 --> 00:09:42,391 V hats. They're essentially the original item 144 00:09:42,391 --> 00:09:46,447 values divided by this magical parameter m, which we haven't yet specified. 145 00:09:46,447 --> 00:09:50,282 But qualitiatively, if m is big, the V hats are going to small and the running 146 00:09:50,282 --> 00:09:53,507 time is going to be fast. On the other hand, if m is small, the V 147 00:09:53,507 --> 00:09:56,687 hats are going to be big and this algorithm is going to be slow. 148 00:09:56,687 --> 00:10:00,942 That's how m controls the running time of this dyanamic programming base heuristic. 149 00:10:00,942 --> 00:10:05,572 Also, remember we argued how intutitively it seemed to be controlling the accuracy. 150 00:10:05,572 --> 00:10:09,957 The more you jack up m, the more information you lose when you round the 151 00:10:09,957 --> 00:10:14,383 Vs and transform them into the V hats, and so, the less accuracy you're going to 152 00:10:14,383 --> 00:10:16,547 have. So bigger m means, on the one hand, 153 00:10:16,547 --> 00:10:19,883 faster running time, but at the cost of worst accuracy. 154 00:10:19,883 --> 00:10:24,623 So this parameter m, really a knob that we can tune to figure out whether we want 155 00:10:24,623 --> 00:10:29,258 a faster algorithm or higher accuracy. The non-trivial statement which we need 156 00:10:29,258 --> 00:10:32,608 to prove in the next video is that there's a sweet spot for m. 157 00:10:32,608 --> 00:10:36,793 That you can simultaneously get a pretty good running time, poloynomial running 158 00:10:36,793 --> 00:10:40,575 time and excellent accuracy. So one trivial observation, but that's 159 00:10:40,575 --> 00:10:44,960 still really nice, is that this dynamic programming based heuristic is guaranteed 160 00:10:44,960 --> 00:10:48,732 to produce a feasible solution. Whatever output of items we get in step 161 00:10:48,732 --> 00:10:51,244 2, it's guaranteed to fit inside the knapsack. 162 00:10:51,244 --> 00:10:55,862 The reason for that is we pass to the dynamic programming algorithm in step 2, 163 00:10:55,862 --> 00:11:00,632 fully accurate sizes, the original Wi's, and similarly a fully accurate knapsack 164 00:11:00,632 --> 00:11:04,302 capacity, capital W. Therefore, the feasible solutions for the 165 00:11:04,302 --> 00:11:08,852 transform knapsack instance are exactly the same as they were in the original 166 00:11:08,852 --> 00:11:12,377 knapsack instance. This explains why we needed to develop a 167 00:11:12,377 --> 00:11:17,452 second dynamic programming algorithm for knapsack, rather than trying to use the 168 00:11:17,452 --> 00:11:20,627 the first one we developed. Thankfully there is this second 169 00:11:20,627 --> 00:11:24,979 computation retractable special case where the items have small sizes and that 170 00:11:24,979 --> 00:11:28,627 turns out to be exactly what you want to make this two-step recipe work. 171 00:11:28,627 --> 00:11:29,315 The analysis is coming right up.