[MUSIC] So far we have studied the bin packing problem and tried to design a linear programming relaxation with the ultimate goal of finding an asymptotic approximation scheme for the problem. Here we will go back a little bit and try to solve some special cases. Why do we do that? Remember that that a linear program of relaxation is our first, our favorite tool to design approximation algorithms. But the attempt we did failed. We failed to have a good linear programming relaxation for linear backing, and so we will try our next meta-tool, our next technique, to design an approximation algorithm. When you are stuck, what do you do? You reduce the problem further. You try to solve some interesting special cases. That helps you develop intuition. For now, we will look at the special case, when all of the items are small. Small compared to the bin capacity. Let's be more specific. How can you solve bin packing more efficiently? When every item has size less than 1/3 of the bin capacity, 1/3 of the bin capacity. Let's do an example. .2,.3,.25,.33,.24,.29,.33,.2, and so on. How does Next Fit perform in this case? What does it do? We can execute it on the sequence and we can see that so far it uses three bins. The first bin is filled to .75 level. .2 plus .3 plus .25. The next bin contains a total of .86. The third bin contains a total of .53, and right now even before we have seen the following item. We could already predict that it's going to fit into bin three. Why? Because it's size is at most one-third. Point five three plus something to a third is less than one. So the next item will fit in the bin. We will be able to add it to bin number three. Something is going here that did not happen before. So, what we can see is that if a bin is filled up to level less than two thirds, then we are guaranteed to be able to fit the next item. If a bin is filled to less than two thirds Then we will never close it. In other words, we only close a bin once it is filled to level at least two-thirds. Since Next Fit closes every bin except the last one, all the bins except the last one Possibly, are filled to at least two thirds. All the bins are filled to at least two-thirds, except possibly the last one. What can we say from this? This is good news! If a bin is filled to two-thirds, then It's already two thirds of 100% capacity. In other words, the total size of the items that are placed in the Next Fit bins is at least two thirds times the number of bins except for the last bin. Much better than before. We this way related the number of bins used by Next Fit to the total item size. We know that up is at least the total item size, so we can combine. And what do we deduce from this? The number of bins used by Next Fit is at most one plus. 3/2 x OPT. 1+ 3/2 x OPT. This is much better than before. Before we had 2 x OPT. Now it's 1.5 x OPT. To prove this we took advantage of the fact that the items were smaller than 1/3 x the bin capacity. So we have just proved a theorem. When all the items are smaller than the one-third of the bin capacity, the next fit algorithm you use a number of bins that is at most 1 plus 1.5 times OPT. So, what is the message from this analysis? From an example with small items to a structural observation, every bin is filled to level two-thirds at least. From that observation, you can deduce an upper bound on the algorithm in terms of the total item sizes. With a different argument we also have a lower bound on OPT in terms of the total item sizes. Combining yields a bounds on bounds with small sizes. This can be extended. What if the items are less than one quarter times the bin capacity? What about one fifth? What about one tenth? What if the items are less than epsilon times the bin capacity? Then, next it is almost optimal, next to the last bin. This is a good exercise. And so, we have seen that in some special cases,when the items are small. It is possible to get a good, a better analysis of bin packing. Next, what we will do is look at some other special case, the opposite case, so to speak, when the items are large. And after that, once we have derived intuition for the two special cases Everything small, everything large. We will be able to combine the intuition and finally analyze an algorithm that is good for every possible input.