0:00

A greedy heuristic for the knapsack problem is pretty good, but let's work a

Â little harder and do quite a bit better. We're going to accomplish a quite

Â ambitious goal. The knapsack problem, being NP-complete,

Â is not we expect going to admit an exact polynomial time algorithm.

Â Let's shoot for the next best thing, arbitrarily close approximation.

Â That is, let's accept from a user error parameter epsilon, and, return the

Â solution whose value is guaranteed to be at least ibe minus epsilon times that of

Â an optimal knapsack solution. So, a client who wants to be guaranteed

Â that this heuristic outputs a solution with a 99% of optimal just has to set

Â epsilon to be 0.01. If this sounds a little too good to be

Â true, there is a catch. The running time is going to increase as

Â we take epsilon to be smaller and smaller.

Â But what this algorithm exports to the client is an accuracy running time

Â trade-off. That is, it exports via this parameter

Â epsilon a knob that the user can turn wherever they want.

Â If you want more accuracy and are willing to wait a little bit longer, you set

Â epsilon to be epsilon to be smaller. If you want something really fast and

Â you're okay with a bit of inaccuracy, you take espsilon to be bigger.

Â And, this is as good as it gets, for Np-complete problems.

Â Assuming P is not equal to NP, there's no way to solve it exactly in polynomial

Â time, the next best thing you can have, hope for, is arbitrarily close

Â approximation, in polynomial time. That is what we will get for the napsack

Â problem using a dynamic programming base heuristic.

Â Sadly, the knapsack problem is the exception that proves the rule. Most

Â NP-complete problems, it is believed you cannot get an arbitrarily close

Â approximation. One concrete example is the vertex cover

Â problem, we discussed exact, expnential time

Â algorithms for vertex cover in a seperate video and we've been talking about

Â polynominal time heuristics for vertex cover, and there are some good ones. You

Â can get within a factor two of an optimum vertex cover in polynomial time, but, it

Â is believed you cannot get arbitrarily close approximation of the optimal vertex

Â cover in polynomial time. In fact, if you came up with such an algorithm, that

Â would imply p equals NP. While there are some other problems out

Â there like knapsack that admit arbitrarily close approximation, there's

Â many more out there which are like vertex cover where, assuming p not equal to NP,

Â it is not possible to get arbitrarily close approximation in polynomial time.

Â But this is an algorithms class, we should stay positive and focus on what

Â you can do. So let's move on to the arbitrarily close

Â approximation for knapsack. So the high-level idea is both very cool

Â and also very natural. What we're going to do is we're going to

Â take the knapsack instance that we're given, so items that have values and

Â weights, and some kapsack capacity. And we're going to massage it a little

Â bit, not too much, just a little bit but we

Â want to put it squarely in one of our computationally tractable special cases,

Â and then, we're going to solve this transformed version of the original

Â input. Now, because we're not solving the

Â problem that we were given, we're not going to get the right answer.

Â But as long as we didn't transform it too much, we can hope that the optimal

Â solution to the transformed problem is a pretty good approximation of the original

Â problem that we were give. Well, what's a computationally tractable

Â special case of the knapsack problem? To date, we do know one, but we only know

Â one so far, which is if we assume that the sizes of the items in the knapsack

Â capactiy are integers, we can go back to our dynamic programing solution for the

Â knapsack problem which runs in time, n, the number of items time capital W, the

Â knapsack capacity. So if it were the case of the knapsack

Â capacity W wasn't too big, if for example, it was polynomial and the number

Â of items, n, then this dynamic programing algorithm would run in polynomial time.

Â For technical reasons, which I'll say a little bit more about later, this

Â computationally tractable special case is not well-suited for deployment in a

Â dynamic programming heuristic. Instead, we're going to want to develop a

Â second similar but different computationally tractable special case.

Â The second special case is when the sizes and the knapsack capacity can be

Â arbitrary, but where the item values are integers that are not too big. This

Â assumption can also be exploited by a dynamic programing algorithm. As we'll

Â show in a separate video, there is a different dynamic programming

Â algorithm for the knapsack problem, whose running time is N squared times the

Â largest item value, N squared times Vmax.

Â So from this second dynamic programming algorithm, we can extract a second

Â computationally tractable special case of the knapsack problem.

Â Namely if all of the item values are small integers, say a polynomial in the

Â number of items n, then this dynamic programming algorithm already gives us a

Â polynomial time algorithm for instances of that form.

Â Armed with the second computationally tractable special case, we can now return

Â to the high-level idea at the beginning of this slide and execute it.

Â Here's how we do it. Our knapsack algorithm is given some

Â knapsack instance, the item values need not be small integers.

Â Now we massage the instance a little bit. We transform it, so that it becomes an

Â instance that we know how to solve in polynomial time.

Â How do we do that? We force the item values to be small integers.

Â How do you take arbitrary numbers and make sure that they're small numbers?

Â Well, the first thing to try is drop the low order bits and that's essentially

Â what we're going to do. Our algorithm then, solves this

Â transformed instance, by construction, the instance has small item value so we

Â can solve it in polynomial time using our second dynamic programing algorithm.

Â Now, we're probably not going to get an optimal solution to the original

Â instance. After all, we solved the wrong instance.

Â Unless we transform the values before invoking our dynamic programming

Â algorithm. But, the hope, and this is just a hope,

Â this is definitely going to require a proof. The hope is that we didn't loose

Â too much information just by throwing out some lower order bits.

Â So, by virtue of computing a solution which is 100% optimal, for the almost

Â correct problem, maybe that solution is also almost optiomal for the fully

Â correct correct problem. So here is the algorithm in full detail.

Â It really only has two steps. Fist, we do the transformation.

Â We round the item values to the small integers,

Â then we invoke the second dynamic programming algorithm on the transformed

Â instance. Precisely, here is how we round each item

Â value v sub i. To begin, we decrease vi to the nearest

Â multiple of a parameter m. I'm going to leave this parameter m

Â unspecified at the moment and therefore this algorithm will be undetermined.

Â Once we start analyzing the algorithm, we'll see what the parameter m has to be

Â as a function of epsilon. So don't forget that epsilon is the

Â accuracy parameter supplied by our client.

Â If the client sets a given value of epsilon, what it means is that our

Â responsibility is to output a feasible solution with value at least one minus

Â epsilon times that of an optimal solution.

Â So the smaller the epsilon, the more accurate our algorithm needs to be.

Â When we round an item value vi down to the nearest multiple of m, we're

Â decreasing it by an amount somewhere between 0 and m.

Â If vi was already a multiple of m, we don't decrease it at all.

Â If vi was just below a multiple of m, then we wind up decreasing it by

Â essentially m. Therefore, the bigger the m, the more

Â information we're throwing out about our instance and the less we should expect

Â our accuracy. That is, the smaller value of epsilon the

Â more accuracy demanded by our client, the smaller we're going to have to take our

Â value of m. Now, once we've made everything a

Â multiple of m, we may as well just scale down,

Â we may as well divide everything by m, we're going to get integers.

Â The integers that we get after rounding down to the nearest multiple of m and

Â then dividing by m are going to be called the V hats.

Â An alternative succinct way to describe the V hats is V hat i is by definition,

Â Vi/m rounded down. And so these funny brackets in blue on

Â the right, that's called the floor operator,

Â that takes in a real number and returns the biggest integer that's less than or

Â equal to the input. Thus, what is the transformation? In

Â effect, we take the item values that were given, we divide them by this parameter m

Â and then we also round down just to make sure we're dealing with integers.

Â Step 2 of our heuristic is to just invoke the second dynamic programming algorithm

Â to solve exactly the transformed instance.

Â That is, we feed into that second dynamic programming algorithm, the instance with

Â N items, the sizes are exactly the same as in the knapsack instance we were given

Â originally. The knapsack capacity, capital W, is

Â exactly the same we were given originally, but we feed in the values, V

Â hat one through V hat n. That is, we solve it with respect to the

Â transformed values, not with respect to the original values,

Â the Vi's. Let's make two quick observations before

Â we conclude. So first of all, remember the dynamic programming algorithm, the

Â second one for knapsack, the running time is n squared times the largest item

Â value, and of course, here we're running the dynamic programming algorithm with

Â these transformed item values the V hats. So therefore, if the V hat are big, then

Â this running time is slow, if the V hats are small, then this

Â running time is going to be reasonable. Now, let's remember the definition of the

Â V hats. They're essentially the original item

Â values divided by this magical parameter m, which we haven't yet specified.

Â But qualitiatively, if m is big, the V hats are going to small and the running

Â time is going to be fast. On the other hand, if m is small, the V

Â hats are going to be big and this algorithm is going to be slow.

Â That's how m controls the running time of this dyanamic programming base heuristic.

Â Also, remember we argued how intutitively it seemed to be controlling the accuracy.

Â The more you jack up m, the more information you lose when you round the

Â Vs and transform them into the V hats, and so, the less accuracy you're going to

Â have. So bigger m means, on the one hand,

Â faster running time, but at the cost of worst accuracy.

Â So this parameter m, really a knob that we can tune to figure out whether we want

Â a faster algorithm or higher accuracy. The non-trivial statement which we need

Â to prove in the next video is that there's a sweet spot for m.

Â That you can simultaneously get a pretty good running time, poloynomial running

Â time and excellent accuracy. So one trivial observation, but that's

Â still really nice, is that this dynamic programming based heuristic is guaranteed

Â to produce a feasible solution. Whatever output of items we get in step

Â 2, it's guaranteed to fit inside the knapsack.

Â The reason for that is we pass to the dynamic programming algorithm in step 2,

Â fully accurate sizes, the original Wi's, and similarly a fully accurate knapsack

Â capacity, capital W. Therefore, the feasible solutions for the

Â transform knapsack instance are exactly the same as they were in the original

Â knapsack instance. This explains why we needed to develop a

Â second dynamic programming algorithm for knapsack, rather than trying to use the

Â the first one we developed. Thankfully there is this second

Â computation retractable special case where the items have small sizes and that

Â turns out to be exactly what you want to make this two-step recipe work.

Â The analysis is coming right up.

Â