[MUSIC] Welcome back to the course on Approximation Algorithms. We are are now going to turn to one of the most famous problems of commonital optimization, the bin packing problem. One of the first NP-hard problems. This is a problem that you've had to face many times probably in your life, without knowing that you were faced with bin packing. Whenever you have to move, you need to pack your items into boxes, and before hand, you have to order the right number of boxes. So you have to figure out how many boxes you need to pack your items. The aim of the bin packing problem is given a set of items, pack them into as few bins as possible. In real life this is complicated by the fact that the objects you pack have various shapes, dimensions, weight. Here we will study the most basic version of the problem, a simplified version of the problem. Where your input has n items, and each item has a single parameter describing it. Its size. Let's say the size is si, for item i. And let's assume by convention, that every item has size at most 1. Then your goal is to pack your items into the fewest unit capacity bins. That's the bin packing problem. Let us describe an algorithm to solve this, a very naive algorithm. Probably the first algorithm you would come up with. In fact, you might even discount that algorithm and try right away to get a better algorithm. But let's try to be as naive as possible. It's called the Next Fit algorithm. What is this algorithm? We just work one bin at a time. At any time we have one open bin that we are trying to fill with items. We take the items one by one in any order, arbitrary order. For the current item we try to place it in the bin, and then maybe it fits maybe it doesn't. If it fits we put it in. If it doesn't fit we close the bin, open a new bin, and put the item in a new bin. That's it. It doesn't get much simpler than that, does it? See this example. In this example we have six items. Of size, 7, 0.7, 0.6, 0.4, 0.3, 0.45, and 0.5. Let's take them in that order. First s1, 0.7. We put it into the first bin. There it is. Next comes item 0.6, there it is. We try to put it in the first bin, but it doesn't fit. So we close the first bin, open the second bin and put 0.6 in there. Then .3 arrives. We can put it on top of 0.6 because 0.6 plus 0.3 is less than 1, so we put that in. And so on. And so you see that the result is you have four bins. You have used four bins to pack your six items. All right, so that's the algorithm. Clearly this algorithm runs in time. It is quick to do. And does it do a good job? It does pack all the items. But doesn't it waste some bins? How bad is it? So, to answer that question, we have to turn to the analysis of the Next Fit algorithm. How do we analyse such an algorithm? In approximation algorithm, we want bound the value of next fit, the number of bins used by next fit, compared to the optimal number of bins by, used by a professional mover who would know exactly what is the best way to pack the items. So let's try some example to develop some intuition. Let me scale things to I can deal with integers. Let's say we have a capacity 100. I'm going to take some items, so let's say random sizes. So I have sequence of items. That all have sizes between 1 and 99. I used next fit to pack them. And in this example, I used 31 bins. Now I look at the result. And I try to see if there is any kind of structure that arises from this input, can we see from this that there is some structure exhibited by the next fit algorithm? Let's focus on bin number seven. Bin number seven contains three items, 25, 14, 25. The next items arrives, 61. But 25 plus 14 plus 25 plus 61 is greater than 100. So, we close bin seven, open a new bin, bin number eight, and put item 61 in bin eight. So what have we seen? We've seen that 25 + 14 + 25 + 61 is greater than 100. The content of bin 7 plus part of the content of bin 8 is greater than 100. In general the content of bin 2i- 1 plus the next item is greater than 100. Why? Because that was the rule for closing a bin. You would not close bin 2i- 1 unless the next item didn't fit, unless adding the next item didn't make it overflow, exceed its capacity. Since the next item goes in to bin 2i, what we know is that the items in bins 2i- 1 or 2i all together have size greater than 100. So in this example, next we've used 31 bins. What can we infer from this? We can infer that bins 1 and 2 together, the sizes of the items placed there is at least 100. 3 and 4 together? At least 100. Bins 5 and 6 together? At least 100. And so on until 29 + 30. All together, the total item sizes must be greater than 15 times 100. So, we have now proved a bound relating the number of bins used by next fit to the total item sizes. The sum of all the item sizes. This is half of the analysis of Next Fit. In general if Next Fit uses k bins. The sum of the item sizes must be at least (k-1) over 2 times 100. Why. The minus one is bi-parative. The loss of bin is special. And then all the previous bins, you pair them up two by two and each pair of consecutive bins the item sizes is greater than 100. And there are k- 1 over 2 of them. That is the other half of the analysis of Next Fit. So far we have given abound on k the number of bins used by Next Fit. Now, we need a bound on opt the number of bins used by the omniscient professional mover who knows the optimal number of bins. Well, even if opt packs each bin perfectly, it cannot do more than fill each bin up to 100. And in that case, OPT uses at least a number of bins equal to the total item sizes divided by 100. The sum of the item sizes is at most OPT times 100. With that, we have related the unknown optimal number of bins to the total item sizes. So we have two relations. On the one hand, the number of bins used by Next Fit, compared to the total item sizes. On the other hand the number of bins used by OPT compared to the total item sizes. All that remains is to combine them. Let's combine. OPT times 100 is at least (k-1) over 2 times 100. What does this mean? Eliminate the 100, rearrange and we get that k, that is the number of bins used by next fit is at most 1 + 2 times OPT. The number of bins used by this very naive algorithm is at most twice as many as the optimal number of bins plus one. So it's, if the plus one was not there, we would call this a two approximation. It's not quite a two approximation because of this plus one, this additional bin. This annoying additional factor. But it's still essentially almost a factor of two at least when opt is large. At least when the items require many bins. So that's what we call an asymptotic two approximation. Asymptotic, as the value of Opt, goes to infinity. Is this tight? Is Next Fit better than this? We have proof that it is roughly effective too, roughly. But maybe it's better than this? Actually, no. It's not hard to come up with an example where the optimal number of bins is 501. But next fit uses 1,000 bins. This is a good exercise. What about non-asymptotic? What about the case when OPT is small? Then it's hopeless. It's hopeless distinguishing between instances such that OPT equals 2, 2 bins suffice. And instances such as OPT is 3, 3 bins are necessary, this is an NP-hard problem. So what have we learned in this section? We have learned that even very crude algorithms can give very good bounds. The message is to try to solve a common item optimization problem, you should first try the simplest possible algorithm. Simplest can perform badly, but sometimes it's already a pretty good algorithm. And the advantage of simplicity is that it tends to be easier to analyze. So if you want to prove theorems, you should always start with the simplest possibility. Keep it simple, is the principle. For a algorithmic design. What about analysis, how can you prove something about your algorithm. You have to first develop intuition, and the message here is that in order to develop intuition, first you have to try executing the algorithm on some concrete examples. So, we have seen the definition of the bin packing problem. A simple algorithm to try to solve this problem. The Next Fit algorithm we have analyzed Next Fit and proved that it is asymptotically to approximation. To get a better algorithm, we will next try to use linear programming.