0:00

Here is the analysis. Step 1 of our algorithm sorts the items

Â in non-increasing order of value per size.

Â Step 2 of our greedy heuristic picks the maximum prefix of items who fit into the

Â kapsack. Let's say that maximum prefix comprises

Â the first k items. The k plus first item is the first one

Â that does not fit in the knapsack given the previous selections.

Â So here is the cool part. Remember we added this step 3 to our

Â greedy algorithm so that it considered two different candidate solutions and

Â picked the better of them. The first candidate solution was just the

Â outcome of step two. So therefore, we can definitely say the

Â output of our three-step greedy algorithm is at least as good as the total value of

Â these first k items chosen in step 2. The second candidate considered in step

Â three of our greedy algorithm is the maximum value item all by itself.

Â So one such item all by itself that would be considered by the greedy algorithm was

Â this k plus first item, the item on which we got stuck in step 2.

Â So therefore, whatever the value of our output of our three-step greedy algorithm

Â is, it's definitely at least the value of item k plus one in isolation.

Â So let's add these two inequalities together.

Â On the left hand side, what do we get? We get double the value of our three-step

Â greedy algorithm. On the right hand side, we get the first

Â k items and also the item k plus one. That is, we get the total value of the

Â first k plus one items. So now, we're in a position to connect

Â this inequality to the fractional greedy solution.

Â So remember, what is the greedy fractional solution, well, it packs the

Â first k items, and then the item in which it gets stuck, namely, item k plus one,

Â it fills up the knapsack fully with a suitable fraction of item k plus one, and

Â the value that the algorithm gets is prorated according to the fraction that

Â it fits in. But what we have here on the right-hand

Â side in green is even better than the greedy fractional solution.

Â This is the first k plus one items, 100% of them.

Â The greedy fractional solution has the first k times, 100%, and some fraction of

Â item k plus one. So, the value of the fractional greedy

Â solution is even worse than the right-hand side here.

Â And the whole point of our thought experiment was to argue that the greedy

Â fractional solution is even better than optimal,

Â that has value at least as much as every feasible knapsack solution.

Â Divide both sides by two and you'll see that we proved the theorem.

Â The output of the three-step greedy algorithm is guaranteed to be at least

Â 50% that of an optimal solution. That's cool.

Â We have a non-trivial worst-case performance guarantee for our simple and

Â blazingly fast three-step greedy heuristic for the knapsack problem.

Â But, maybe you were hoping to do a little bit better than within 50% of an optimal

Â solution. Maybe in the back of your mind, you were

Â really rooting for something like 90% or even better.

Â There's a few roads we can take that might lead to better performance

Â guarantees. The best case scenario is if we could

Â just sharpen our analysis of this greedy heuristic, that is, don't change the

Â algorithm, don't make any new assumptions, just have a better proof and

Â maybe the 50% one prove to some other number.

Â That would be the best case. The second thing we could do is if we

Â really love this algorithm, for example, it being so fast, we could try to

Â identify additional assumptions on instances that allow us to prove better

Â performance guarantees than this 50% guarantee which holds for all instances.

Â The third thing we're going to try to do is just come up with a better algorithm,

Â that in fact, has better performance guarantees, so what I want to show you on

Â this slide is that the first case, the best case scenario of just sharpening the

Â analysis of this greedy algorithm, is not feasible The analysis cannot be

Â sharpened. [INAUDIBLE] the 50% can be realized for

Â certain instances. Then, we'll tackle the other 2

Â approaches, and we will in fact get better performance guarantees, either

Â under extra assumptions about the instances, or alternatively, using a more

Â sophisticated algorithm. So here's an example that shows that

Â there really are knapsack instances on which this 3 step greedy algorithm might

Â obtain merely 50% of the value of an optimal solution.

Â In this example, we're going to set the knapsack capacity, capital W, to be 1000.

Â There's going to be three items. Item one will have a value of 502 and a

Â size of 501. The second and third items are going to

Â be identical, both are going to have value 500,

Â both are going to have size 500. So what is the greedy algorithm going to

Â do? Well, in step 1, it sorts the items according to the value for, per size

Â ratio, and you'll notice that the first item has a ratio slightly bigger than

Â one, so it's going to be considered first

Â before items two or three. In step 2 of the greedy algorithm, it

Â packs item one in the knapsack, that leaves only 499 units of residual

Â capacity, not enough room for either item two or item three.

Â So step 2 of the greedy algorithm just outputs the first item by itself.

Â Step three of the algorithm considers the max value item in isolation,

Â that again is item one. For this reason, the greedy algorithm

Â will output the solution which is just item one for a value of 502.

Â And I'm sure you've noticed that there's a better solution if you [INAUDIBLE] item

Â one and instead choose items two and three.

Â They both fit in a knapsack, they fill it fully,

Â for a combined value of 1000, which is essentially twice as big as the value of

Â the greedy solution. So what does this example teach us? Well,

Â it argues that if we want perfomance guarantees better than 50%, we have one

Â of two options. First, if we really want to keep

Â analyzing our three-step greedy algorithm, we're going to have to make

Â extra assumptions about the instances. In order to prove performance guarantee

Â is better than 50%. There are some instances out there where

Â the performance is bad as 50% of optimal. The second approach we can take is to

Â look at better algorithms which might have better guarantees on worst case

Â instances. So in the next slide, I'll show you a

Â refined analysis of the three-step greedy algorithm, conditions under which it

Â performs much better than 50%. In a separate sequence of videos, we'll

Â develop a dynamic programming base heuristic,

Â which is guaranteed to have much better performance, on all instances.

Â So there's a few different assumptions you can impose on knapsack instances that

Â will enable you to prove better performace gurantees for greedy

Â heuristics. Let me just show you one, that's both

Â simple and also it's a condition that's met in many knapsack instances that arise

Â in practice. So let's focus on knapsack instances

Â where no item is especially big compared to the knapsack capacity.

Â For concreteness, let's say that the size of every item is at most 10% of the

Â knapsack capacity, capital W. As you'll see, there's nothing special

Â about the number 10%. I'm just using that to keep the

Â discussion concrete. So I claim that without changing our

Â algorithm at all using exactly the same three-step greedy algorithm.

Â Actually, here, we can even get away with the original two-step greedy algorithm.

Â We can prove performance guarantee is much better than 50% as long as the

Â instance satisfies this property. Why is this assumption useful? Well, lets

Â think about step 2 of our greedy algorithm.

Â So we've sorted the items in non-increasing order, of value per size.

Â We're packing the items one at time. Now, at some point we get stuck, there's

Â some item k plus one where if we tried to put it in the knapsack, we would overflow

Â the capacity. Well, by assumption, this k plus one'th

Â item, its size is at most 10% of the original knapsack capacity.

Â So if sticking in item k plus one would cause it to overflow, that means there's

Â less than 10% of the knapsack capacity currently available.

Â That is, the knapsack is currently 90% full, or more with the items that we've

Â already packed in so far. So this is sounding pretty good.

Â Our greedy criterion ensures that whatever fraction of knapsack we wind up

Â using, we're using in the most valuable possible way and we just noticed that

Â this assumption on the instance, implies that we use almost all of the knapsack.

Â To make this intutition precise, we comapre the output of our greedy

Â algorith, even just step two, to our favorite hypothetical benchmark,

Â mainly, the greedy fractional solution. What's the difference between these two

Â solutions? Well, they're almost the same, the only difference is that the greedy

Â fractional solution gets to pack that last bit of the knapsack, which we know

Â is at least 10%, with a suitable fraction of item k plus one.

Â So, the value that we're missing in our solution is that final 10% at most of the

Â greedy fractional solution. Now in the greedy fractional solution,

Â the items are packed in decreasing order of bag per buck and a value per size.

Â So, this last 10% of the greedy fractional solution is also the least

Â important. It's making the least valuable use of capacity.

Â So this final at most 10% of the greedy fractional solution can account for, at

Â most, 10% of its overall value. So whatever we're missing in our solution

Â for our greedy algorithm, it's at most 10% of the overall value of the greedy

Â fractional solution. That is, we're getting at least 90% of

Â the value of the greedy fractional solution. And we know from our thought

Â experiment that the greedy fractional solution is even better than optimal, is

Â at least as good as any feasible knapsack solution, therefore, the output of our

Â greedy algorithm, even if we don't use the third step, is 90% as good as the

Â value of an optimal solution. All of this reasoning holds equally well

Â with a number different than 10%, so for example if you only knew that

Â every size was at most 20% of the knapsack, then you'd get that the greedy

Â solution would be at least 80% of optimal.

Â On the other hand if you knew that every item had size at the most 1% of the

Â knapsack capacity then just the two-step greedy algorithm would get you within

Â 99%.

Â