In the previous lessons, we looked at the load balancing problem, and we gave a very simple Greedy algorithm for the problem. That algorithm just goes over the jobs one by one, and it assigns each job to the machine that at that point in time, has the smallest load. We proved that the simple Greedy algorithm is actually 2 minus 1 over m approximation algorithm. This 2 minus 1 over m is tight. So, in this lesson, we're actually going to give a new algorithm that has a better approximation ratio. So, let's remember what the problem was with the simple Greedy approach. If you look at this particular input where first, you have two jobs of size one and then, you have one job of size two. The Greedy algorithm will first assign the two jobs to the two different machines, and then, place the one job of size two on top of one job of size one. So, the total makespan for this example would be three, but it's easy to see that the optimal makespan for this particular input would be two. So, one way to look at this problem is that actually, if you have a very large job at the end, the algorithm does not perform well. So, what's a simple solution to this problem? Well, let's make the algorithm handle the jobs in an ordered manner. So, let's first sort all the jobs by size from largest to smallest, and then let's run our old Greedy algorithm with the jobs in this new order. So, let's look at a simple example on the problematic case that we just saw. So, before we run our Greedy algorithm, we're first going to sort the jobs by size like this, and now we run the Greedy algorithm so the first one goes to this machine at one, and then the other two are going to go to the other machine. So, what we see in this case is that our new algorithm actually computes an optimal solution. So, could it be that our new algorithm actually always computes an optimal solution? Well, hopefully, you realized that the answer must be no, load balancing is an NPR problem, this ordered scheduling algorithm runs in polynomial time, so we cannot expect that it always computes an optimal solution. Here, you see an example where indeed the solution computed by our ordered scheduling algorithm will not be optimal. So here, the input is already ordered, so if we sorted nothing changes, and what our algorithm is going to do? Well, the first two jobs of size five are going to machine one and machine two, and the remaining three jobs each having size three are now put on top of these jobs. As you can see, the makespan of this solution is 11 but it's also easy to see that you can actually have a better solution of makespan 10 if you simply put the two jobs of size five together on one machine and the three jobs of size three on the second machine. So, here our ordered scheduling algorithm is not optimal. But we can still show that it's actually better than what we had before. Remember that the simple Greedy algorithm had an approximation ratio of 2 minus 1 over m. So, if m is large, this goes to two. Well, here we can show that are ordered version where we first saw the job's always has an approximation ratio of 1.5. So, let's see if we can prove that. Remember that the general scheme of such a proof is that you, well, you consider an arbitrary instance, and then, you want to prove that for that arbitrary instance, the value of the solution that you compute is at most, well, first you show 1.5 times the lower bound, and then, that implies that it's at most 1.5 times the optimal value. Okay. So, if we want to apply this general scheme here, then, well, besides the lower bound that we had before, we actually need a new component. Remember that in the previous lower bounds, we had two components. First of all, we said that well the optimal can never be better than the average load of all the machines, and the average load is the sum of all the loads of all the sizes of the jobs times 1 over m, m is the number of machines. So, that's one lower bound, a different lower bound is simply the size of the largest job, the max of all the t_js. To prove that our ordered scheduling is a 1.5 approximation, we will need a third component in our lower bound. So, let's have a look at what the third component is. So here, you see a set of jobs that are sorted by size. The largest job first and then they get smaller. Now, let's assume here that the number of jobs is at least n plus 1. If the number of jobs is at most m, the number of machines, then every job can get its own machine and that's not very interesting, so let's look at the case where m, sorry, where the number of jobs is at least n plus 1. Now, let's look at the first n plus 1 jobs. If we have n plus 1 jobs and only n machines, then obviously, one of the machines gets at least two of those jobs. What does it imply? Well, the smallest two possible jobs, since they're sorted, are the last two in the sequence, so t_n and t_n plus 1. So, there will be a machine that gets two jobs, and the total load of these two jobs is at least t_m plus t_m plus 1. So, that's another lower bound. Okay. Now, we have the lower bound in place, now let's see if we can prove that our algorithm is a 1.5 approximation. So, let's go back to the proof. Remember that we had some important definitions in our proof. So, one of the things was we defined M_i star, that's the machine that determines the makespan, so the machine with the largest load. Another important definition was job number j star. That's the last job which is put on this machine that determines the makespan. Finally, we defined load star to be the load on this machine just before this last job was assigned. As you see in the picture, this means that the makespan is equal to the load star of M_i star plus the processing time of this job j star. Okay. Now, let's go back to the proof. So again, what we have to do is we have to look at an arbitrary problem instance I, and then, well, we have two cases. First of all, what we already said before, let's look at the case where this last job j star, so the last job assigned to the machine that determines the makespan. Suppose the number of that job is at most m, and remember that the first m jobs, each get their own machine. So, this would mean that this job j star gets its own machine because it's the last job assigned to M_i star. Well, if the makespan is determined by machine that gets only one job, then clearly, the solution is optimal. So, now look at the more interesting case where j star, so the number of the job that determines the makespan is actually at least m plus 1. So, this is the interesting case and let's see what happens. Well, remember that the total processing time on our machine M_i star is equal to load star, the process in time just before this last job was assigned, plus t_ j star. We want to show by some computation, so this is at most three over two times the lower bounds, which then implies that it's at most three over two times opt. Remember that the lower bound, well, had these three components: One, the average load of older machines, two, the maximum load on any of the machines, three, this t_m plus t_m minus 1, and that's something that we're going to use now. So, let's look again at this load star plus t_j star, and in particular, let's look at t_j star. What can we say about t_j star? Well, we're now in case two, so j star is at least m plus 1. What does it mean? Well, it means because the jobs are sorted, that t_j star is at most t of m plus 1. Because if you put them in order and then the job j star is m plus 1 or something further, but it was in sorted order, so t_ j star is at most t_m plus 1. That's, again, because the jobs are sorted is at most one half times t_m plus t_m plus 1, because t_m is at least t_m plus 1. So now, we can replace this t_j star by, well, what we have here, one half times t_m plus t _m plus 1. Now, we can simply follow what we did before. Well, the first component is 1 over m times the sum j equals 1 to j star minus 1 of t_j, we can do the sum all the way up to m. Now, what you see is this first term is again one of the components in our lower bound. The second term is one half times this new third component of our lower bound. So, this is simply 3 over 2 times the lower bound which is at most 3 over 2 times opt. So, this is nice. We've shown that our new ordered scheduling algorithm actually always gives at most 1.5 times the lower bounds or at most 1.5 times opt, so we have a 1.5 approximation algorithm. Actually, it performs even better and similarly to what we did for the analysis of the Greedy algorithm, where we first prove that it was a 2-approximation, and then looked a little bit more carefully at the proof and derived that it was actually a 2 minus 1 over m approximation algorithm, we can do something similar here and that would be a nice exercise for you. So, instead of 1.5 approximation, you can actually show that it's a 1.5 minus 1 over 2m approximation algorithm. So, let's summarize. So, what we've seen was in this whole series of lessons, well, we looked at the load balancing problem and we first gave a Greedy algorithm for that problem. Then, we analyzed that algorithm. In the analysis, it's very important that we do not directly compare the quality of our solution to opt because we don't know opt, but we compare it to a lower bound. So, we came up with a lower bound and then proved that our algorithm was at most two times this lower bound. So, we have a two approximation. Then, we looked at a slightly more careful analysis and we proved that it's actually a 2 minus 1 over m approximation. Then, well, for this algorithm the 2 minus 1 over m was tight, so if we want to do something better, we have to come up with a new algorithm and that's exactly what we did. We came up with ordered scheduling where you first sort the jobs by size, and then apply the Greedy strategy, and then we prove that this gives a 1.5 approximation. As I just said, actually the bound is even a little bit better than that. So, in the remaining lessons, we're going to do a lot of other things on approximation algorithms. First, we're going to look at the so-called Vertex Cover problem and get an approximation algorithm for that. One of the nice things is that, at least for the weighted version of this problem, to do that, we will need a very general technique called LP relaxation, which you can use for a lot of problems to get approximation algorithms. Then, after that, we will have another series of lectures where we're going to look at so-called polynomial time approximation schemes. These are very powerful approximation algorithms where the approximation ratio that you get, you can actually get it arbitrarily close to one. So, the solution will almost become optimal, but that's for later.