[MUSIC] We have done so far a detailed study of vertex cover. But that's not really what this course is about. It's not so much about solving specific problems as it is about developing techniques. Teaching how to solve problems, teaching a methodology. So, let us review what we have learned so far in that respect. What is the method that we applied in the case of our desk cover? Designing an algorithm. We have seen on this example how to do it in three steps. First, find a integer program to model the problem. Second solve a linear programming relaxation. Third round the solution to get an integer solution. That is a standard algorithm technique used for approximation algorithms. We will see this over and over again in this course and it is good to remember this as a standard technique. How do we analyze such an algorithm? There are three things that need to be done. First, when you try to get such an algorithm, you need to verify that it really is correct. That the output really satisfies the conditions. Second, you must verify that it really is efficient, where efficient in this class means polynomial time, the run time must be polynomial. Some people are not so happy with such a definition, but we are theoreticians. We want polynomial run time, that's our definition of efficiency. Third and most importantly how good is the solution? You must analyze the value of the output solution and show that it is within a certain factor of the optimal value. Here the fact that we showed was a factor of two. Soon, we will see an algorithm where the factor is one plus epsilon. Sometimes it can be login sometimes it could much worse. Finally, for this kind of algorithm, there's a particular method to try to analyze the quality of the output. The method is to go as an intermediate step through the LP value. You must, on the one hand, relate the output to the LP value. On the other hand relate OPT to the LP value and then it only remains to combine the two things. The method for the analysis of the quality of a solution is focus on the value of the linear program. Now let me say a few more words about vertex cover. We could say many more things about the vertex cover problem, but let me just address the question of the quality of approximation, this factor. We have a two approximation. How much better could we hope to get as an approximation algorithm? Could we solve vertex cover optimally? No. Dick Karp in 1972 proved that vertex cover is NP-complete. This was one of his original NP-complete problems in his famous paper where he listed a few problems from diverse areas and proved them all NP-complete. Then, can we hope to get something arbitrarily close to one? An approximation that is one plus epsilon for every epsilon? An approximation scheme, as we call it. No, impossible. Why? Christos Papadimitriu. Mihalis Yanakakis. In 1991, they proved that you cannot get better than some very small number, something like 1.001 of the optimal value. Getting bellow that is anti-complete. So if p is different from np, of course, you cannot hope to get arbitrarily close to one. But that number is really quite small. Can't you prove something better than this? Yes. In the early 2000s, Yacreet Dinur and Moolie Safra showed that you cannot hope to get better than 1.36 approximation for vertex cover if p is different from np. To date, it's the best result, assuming p is different from np with no other assumptions. But, we also have another result, a conditional result. If a certain conjecture is true, the unique games conjecture, then our two approximation algorithm is optimal. It is impossible to get in polynomial time something that would be strictly less than two, a 1.999 approximation. This is a result by Subash Khot and Regev from 2003. So what can we say? Vertex cover is hard in the worst case. Finally, to conclude this part of the class, I would say that we have so far designed a method for approximation algorithms, applied it to vertex cover, and proved that it's a two approximation. On the way to doing that, we have had a little fun with vertex cover. I could say many more things about it, but this is enough for this particular problem.