In the previous lessons, we looked at the definition of rho approximation algorithm, and we looked at the rho balancing problem. We gave a very simple greedy algorithm for the rho balancing problem. In this lesson, we're going to analyze this algorithm and prove that it's actually a 2-approximation algorithm. Let's first recall the definition of rho approximation algorithm. An algorithm for an optimization problem or for a minimization problem is a rho approximation algorithm, where rho is some value greater than one, if the value of the solution that our algorithm computes is at most rho times the optimal value for any possible instance I. Okay and the big question is how can we actually prove that this is the case, because the problem is we don't know what OPT is? If we could compute OPT, then we would not need an approximation algorithm. So, the question is, how can we prove that something is at most rho times OPT, if we do not know OPT? So the way to go about this is the following. Instead of comparing the algorithm to the optimal solution, we're going to look at a lower bound on the value of an optimal solution. Then, if we have a lower bound and we can prove that our algorithm is at most rho times this lower bound, then it's also at most rho times OPT. This is for minimization problems. For maximization problems, we would need to work with an upper bound on the value of an optimal solution. But here we're going to look at the rho balancing problem which is a minimization problem, so we want to work with a lower bounds on the value of an optimal solution. So, let's try to develop a lower bound for our rho balancing problem. So, the first observation is that since we must assign all the jobs to one of our machines, that's what a valid solution would be, that if you take the sum of all the processing times, the sum of j equals one to n, the sum over all the jobs of tj. Now I multiply by one over m, m is the number of machines. Then this will be the average load of all the machines. Obviously, the maximum load of any of the machines, which determines the makespan, is at least the average load. So, this one over m times the sum here is a lower bound on OPT. OPT can never be better than this. There's also a different very simple lower bound which we get if we observe that the largest job, obviously the largest job must go somewhere. So, even if I have one large job and lots of small jobs, even if the average load is quite small, then this large job must still go somewhere. So the size of the largest job is also a lower bound. So the lower bound that we're going to work with is what you see here, our OPT is at least the maximum of these two numbers. So, the maximum of the average load and the maximum load of any of the jobs. So now, if we want to prove that our greedy algorithm is a 2-approximation- this is the lower bounds and I forgot to say we denote it by LB, for lower bound of I. So, now let's see what we can do if we want to prove that something is a 2-approximation. So, if our algorithm, our greedy algorithm for load balancing is a 2-approximation, in general, the proof will have the following structure. We look at an arbitrary instance I, because we have to prove that our algorithm is at most two times OPT for any possible instance I. Then we're somehow going to prove that the value of the solution that we get, is at most two times this lower bound. Then, because it's lower bound, by definition is at most two times OPT. So that's the plan for our proof and let's see how we can make this work. So first before we can give the proof, I need to give a few definitions. So let's look at the solution that our algorithm computes. So here, you see a picture for some example. So first, let's look at the machine that determines the makespan. So that's the machine with the largest load, and I denote that machine by Mi*, so i* is the machine with the maximum load. So here this will be the third machine. So remember Mi* is this machine that determines the makespan. Now let's look at the last job that we put on that machine, and that job I denote by Job j*. So that's this one, it's the last job that goes onto the machine that determines the makespan. Let me define Load* to be the load of the machine just before this last job was assigned. So that's going to be this. This is Load* of Mi*. Obviously, if you look at the difference between this Load* and the makespan, well, it was the last job assigned to that machine, so the difference is just the processing time of that job, so t of j*. Now we have our definitions in place, so let's try to prove that we have a 2-approximation. So here's our picture again, where you see our Mi* and you see Load* and so on. So, what is the value of the solution that we compute? So what is greedy scheduling of our instance I? Well, by definition of what we just said, it's the Load* on Mi* plus the processing time of this last Job j* that was scheduled on that machine. So let's look at Load* and see if we can say a little bit more about it. Well, I claim that Load* of Mi* is at most one over N times, and now we take the summation of j equals one to J* minus one, so that's all the jobs before j* of tj. So, let me go a little bit out of the way, so you can see it a little bit better. So this I claim that load star is at most this quantity. Why is this the case? Well, if you think about how the greedy algorithm works, it's going to assign j* to the machine that at that moment has the smallest load. So obviously the smallest load at that moment is at most the average load of that moment. This average load is exactly what you see here, it's the sum of all the loads so far. So up to j* minus one, and then we take that sum and we take the average of the the machine, so multiply by one over m. So I can replace my Load* of Mi* by one over m times the summation, plus, well, I still left this tj*. Now, let's do the following. If you look at the summation here, instead of only doing the summation all the way up to j* minus one, I'm going to do the summation over all the jobs. So I'm going to look at the sum all the way up to n. Obviously, that will give me an upper bound on the previous summation. So, that explains the next line. Now what we observe is that what we have here is closely related to the lower bound that we previously had. So, remember that the lower bound that we had was, well, on the one hand, it's the maximum size of any of the jobs. So the max over all tjs. The other component was the average of the sum of all the loads. You see exactly the two terms that we have now, we can nicely bound using this lower bound. The first term that we had in our formula is exactly one of the ones in the lower bound. The second term, this tj*, is of course at most the maximum of any of the tjs. So, this is simply at most two times the lower bounds, which has at most two times OPT. So what you see is that what we did by comparing the quality of the solution that we get to not directly to the optimal solution, to the value of the optimal solution, but to a lower bounds. Then we could say something, and we find that it's at most two times the lower bounds, and then we also proved that it's at most two times OPT. This is going to be always the case when we prove something about approximation algorithms. For minimization, we're going to compare the algorithm to a lower bound and then we can conclude also how it relates to OPT. Okay. So, the theorem that we proved is that our algorithm greedy-scheduling is a 2-approximation algorithm. So, the question is well, 2-approximation may be you want to get a better approximation algorithm. 1.5, maybe even 1.1, can we do that? Well, in general, if you have an approximation algorithm and you prove that it's a 2-approximation, if you want to do better, there are three ways of doing that. First of all, you can simply look at your proof and maybe in your proof you can do something smarter. You don't change the algorithm, you don't change the lower bound that you compare it to, but what you do is you look at your proof and maybe it's some slack there that you can use to improve and get a better approximation ratio. The other thing that you could do is you could have the same algorithm, but maybe your lower bound is not so good. If your lower bound is far away from OPT, then your proof, the approximation ratio, will also be far away from OPT. So, maybe if you can come up with a better, a smarter, lower bound that is closer to OPT, you can get a result that is closer to OPT. Okay. The third option is, just come up with a different, more clever, a better algorithm. So, what we're going to do now is the first thing. So, we're not going to change the algorithm, we're going to look at the same lower bounds but the difference is we're going to look at the proof and we're going to see that there's one point in the proof where we can actually be a little bit more precise and that way get a better bound. Okay. So, let's see how this works. So, we want to improve the approximation ratio by looking at the proof and see where we can be a little bit more precise. So, let's look at the proof. So, you see the lower bound and you see the proof that we had. Well, if you look at this proof, if we compare the second and the third line, then you see what we do is, we first had this summation where we sum all the way to j star minus one, and then in the next line we replaced it by a summation where we go all the way to n. And these two things can never be the same because there's always the job j star which is not in the first summation, because we only go to j star minus one, but which is in the second summation. So, what we can do is we can use this inequality that says that if I only sum two j star minus one at most that value that you get is at most well, if you sum all the way up to n to the nth job, but now subtract the load or the processing time of job number j star, because that's definitely not included in the first summation and it is included in the second one. Okay so, when I use this inequality, then I get a better bound. So, instead of this, I now replace it by what you see above. So, I subtract this tj star. Now, let's rewrite this a little bit. So, what happens is that the tj star I move it out of the summation in the right term and then you get that well, the first term that you see is still the lower bound but the second one, this tj star, is now multiplied by one minus one over m. Okay, and this one over m is a slight improvement. So, in total, I now get well, the first term was lower bound, second term is one over m times tj star. Tj star is also at most the lower bound so in total I get two minus one over m times lower bounds and again, we can conclude that this is at most two minus one over m times OPT. Okay. So, what we did was we did not change the algorithm, we did not compare to a different lower bound, but we just looked more carefully at the proof and we saw that there was one place where we would actually gain a little bit in the analysis. So, actually we have proved that, it's also 2-approximation, but actually it's even a two minus one over m approximation. So, you see that now the approximation ratio starts to depend on the number of machines. For two machines, m is two. You would actually get a 1.5 approximation. For three machines, you would get a five over three approximation. So, this is better than two, but you see the larger the number of machines the closer to two the approximation ratio will get. So, we have proven this nice theorem and well, again we can ask ourselves the question, can we do better? Can we get an algorithm that is better than a two minus one over m approximation? Okay. Remember there were three ways of doing it. We could either work with the same algorithm, the same lower bound, but well, be more careful in the proof. That's what we just did. We could also look at the same algorithm but maybe have a better lower bound, a lower bound that is closer to OPT and then that would give us the possibility to prove something closer to OPT. Or maybe we can do a completely new algorithm. Okay. So, let's see if it's actually possible with this algorithm, maybe with a different lower bound, to prove something better than the two minus one over m. Okay, and actually it will turn out that this is not possible because of the following problem. So, let me try to give an example just for two machines with the following input sets. So, we have two machines and the size of the jobs, the processing times of the jobs, is well, three jobs. Job of size one, another job of size one, and one job of size two. Okay, if you think about it you will probably immediately see that what will happen is the following. First job goes to machine one, second job to machine two, and then the third job to let's say machine one. So, I have a make span of three, but obviously it will be better to have the two jobs of size one on the same machine and the job of size two on the other machine. So, in this case, our algorithm will give something with make span three, the optimum is two. So, here the approximation ratio, the ratio between these two values, is three divided by two. And for two machines, this is exactly the same as two minus one over m. Okay. So, that means that here we have an example where our analysis is tight. Where we have shown that the greedy algorithm, what we get, is exactly equal to two minus one over m. So, we can try what we want in better proofs or different lower bounds, but this is simply what can happen. So, there's nothing we can do. If we want to do better than two minus one over m, we really need to come up with a different algorithm. So, well, the third two options are not possible so what we need is a different algorithm and that's what we're going to do in the next lesson. So, what we've seen here is well, first of all, that greedy-scheduling is a two minus one over m approximation algorithm. Okay, and what is very important to remember is that if you want to prove something like that, you do that by proving that it's at most two minus one over m times a lower bound. So first, you have to come up with a good lower bound and then you can try to prove something like this. We also saw that this approximation ratio, two minus one over m, is actually tight for this algorithm. So, there's no way to give a better analysis because sometimes it actually happens that you really get the two minus one over m. So, in the next lesson, we're going to change our algorithm, not much, but we're going to change it a little bit and then actually we're going to beat this two minus one over m bound.
