[SOUND] Welcome to this last series of lectures on approximation algorithms. So what did we see so far? Well, we started by giving some basic definitions of approximation ratio and Swan. Then we looked at an example, load balancing. And then we looked at LP relaxation which is a very nice and general technique to obtain approximation algorithms. Our last series of lessons is going to be on so called polynomial-time approximation schemes. So I hope you remember the basic definition of a role approximation algorithm. It's an algorithm that for any possible problem instance I, computes a solution. Which for minimization problems is at most row times the value, it's row times the value of an optimal solution. Obviously the closer rho is to 1, the closer we get to the optimal solution, all right? So we would really like to get something very close to rho = 1. So the main question is, how close to one can we actually get? Well that depends on the problem. For instance, if you look at the vertex cover problem, we gave a 2 approximation algorithm for that. But actually, it turns out that maybe it would be possible to do a little bit better although nobody has come up with a better algorithm so far. But at least, we know that you cannot do better than getting roughly a 1.36 approximation algorithm. So in particular, you cannot get arbitrarily close to 1. For some other problem, however, we can get arbitrarily close to 1. In other words, if you tell me, I want a 1.1 approximation, then I say, okay, here, you have a scheme that gives a 1.1 approximation. If you say, I want a 1.01 approximation, I can also do it, okay? So let's see how that works, and let's try to define this a little bit more formally. So a polynomial-time approximation scheme is, well, an algorithm that takes, of course, an input instance as input. But it also gets as input a second parameter, which is some value epsilon greater than 0, okay? And using this epsilon, the user can control how close to the optimal solution, the solution computed by the algorithm is going to be, okay? So more formally, when is this algorithm ALG with these two parameters, input and epsilon? A polynomial-time approximation scheme or PTAS as we usually say for short. Well, first of all, the approximation ratio has to be 1 + epsilon, okay? So the value computed by our algorithm, so ALG I and epsilon is at most 1 + epsilon times OPT for a minimization problem. Secondly, as with all approximation algorithms, the running time should be polynomial, okay? Polynomial in the size of the input. So let's look at this a little bit more closely, because the running time now not only depends on the input size. It actually also depends on this parameter epsilon, which is what you expect. Because if you want to get something which is much closer to the optimal solution, somehow you have to pay. And in this case, it means you have to pay in terms of running time. The smaller you make epsilon, the slower your a logarithm will be. So let's look a little bit at this dependent on epsilon. So here, you see various possible running times, and as you see if I denote the size of the input by n, then the running time is the function of this n. And the dependency on this n should be polynomial, but it also depends on this epsilon, okay? Note that the dependency on n, the size of the input should be polynomial. So something like you see here, where there's a 2 to the power n, which is exponential in n, is not allowed, okay? So these three running times, they are simply polynomial in n, and so they are fine. So what you'll also see if you look at the dependency on epsilon, these three examples, they're sort of two different categories. The first example the running time is not only polynomial and n, but also the dependency on 1 over epsilon, that dependency is also polynomial, okay? The second and third example of running time you see, there the dependency of 1 over epsilon is not polynomial. It's exponential. Well obviously, it's nice if not only the dependency on n is polynomial, but also the dependency on 1 over epsilon. So for this polynomial time approximation schemes where also the dependency on 1 over epsilon is polynomial. There's a special name and they are called fully polynomial-time approximation schemes or in other words FPTAS. Okay, so this is the basic definition for minimization problems. Well, I guess you could probably already come up yourself with how to adapt this definition for maximization problems, okay? For maximization, it simply means that the approximation ratio is now not that the solution is at most, 1 + epsilon times opt. But it should be at least 1-epsilon times OPT, all right? Again, we want to get arbitrary close to approximation ratio 1, and in this case, that means that you get is 1-epsilon. Okay, so what we're going to do in the next lessons is we're going to look at an example of a polynomial-time approximation scheme. And this example is going to be for the Knapsack Problem, and the nice thing of this example will be that it uses a general technique to obtain a PTAS, to obtain a polynomial-time approximation scheme. And this technique can also be applied two different problems, does not only apply to the Knapsack Problem. [SOUND]
