In the previous lesson, we looked at the vertex cover problem and we gave a very simple algorithm that unfortunately does not give a good approximation ratio. In this lesson, we're going to do better and we're actually going to get a two-approximation for the problem. So remember what the problem with the previous algorithm was. If you have the star graph, what the algorithm was doing, it was looking at an edge, which is currently uncovered and then put one of the vertices into the cover and if it was unlucky and it kept doing this, then at the end, all non-central vertices would end up in the cover and the approximation ratio could be V minus one. So when V, the number of vertices is large, this would give a terrible approximation ratio. So now, we want to do something more clever. So, let's see what we can do. The first thing you could think was maybe, well, let's try to be clever in deciding which of the two vertices to put into the cover. Well, that's very hard to do. So, what we're going to do instead is something that looks stupid, namely put both vertices into the cover. Well, it may look stupid, but actually it turns out that this will give us a two-approximation. So, let's look at the algorithm again. So here, we see our old algorithm that we had before, okay? Initialize the cover to the empty sets, the uncovered edges initially, the old set of edges. Now, taken uncovered edge, put one of the vertices into the cover, remove the edges that are now covered, and so on. So, as I said before, what we're going to do now is instead of putting only one of the vertices into the cover and trying to be smart by maybe deciding which one to put, we decide to be well, kind of stupid maybe and just put both into the cover. Okay,and as you see in the example here, this works great because now we're sure to also put the central vertex, and suddenly we have covered all the edges in our graph. So, this is the idea, this is our algorithm. Now, let see if we can prove that it's a two-approximation. So here's the theorem, this new algorithm is a two-approximation. Remember that the general setup of the proof of such statement is that we're going to look at the value of the solution, so the size of the cover in this case generated by our algorithm, and then prove that this is, at most, well, if we want to have a two-approximation, at most two times the lower bound. Again, that immediately implies that it's at most two times the optimal value. So, the first thing we need to do is we need to come up with a good lower bounds. So let's try to see how we can do that. So, the important concept for the lower bound that we will be using is the concept of what I call disjoint edges. So when our two edges disjoint? Well, if they do not have an endpoint in common. So for instance, these two edges are disjoint, these two edges are disjoint, but these two edges are not disjoint because they have an end point, a node in common. So now, we have this concept of disjoint edges. How can we use that to come up with a lower bound? Well, that's as follows. If you have a set, and here I said E star of edges. So, this is a subset of the edges, with the condition that all these edges are disjoint from each other. Then I claim that opt for this instance, so the minimum number of vertices you need to put into the cover, is at least this number of edges, this number, e star. Why is that? Well, obvious, because for any two edges, you need to put one of the two end points, but that endpoint is not useful for any of the other edges in E star because they're disjoint. So, this E star, the size of such a set E star is a lower bound for our algorithm. So now, using this lower bound, let's try to see and let's try to prove that we get a two-approximation. So, if you look at this algorithm, what you see is that in line three, we select an edge uv, then we put both vertices into the cover and then in step five, we're going to remove all the edges that are either have U as an endpoint or V as an endpoint. So that means that every edge that is left must be disjoint from this edge uv. So, in other words, if you look at the edges that are selected over the course of the algorithm in line three, that's a set of disjoint edges. Okay. What you also see is that if you look at line four, so in line four, it says once we select an uncovered edge in line three, we put both vertices into the cover. Well, that simply means that the total number of vertices we put into the cover is equal to two times the number of selected edges. So, now we have all the ingredients and we can finish our proof. So, we look at an arbitrary graph G. Okay, now our new algorithm, approx vertex cover. Well, the number of vertices we put into the cover is at most actually equal to two times the number of selected edges. Well, the selected edges, as we saw, are disjoint from each other, but that means that the size of the set of selected edges is a lower bound. So, what we get is two times the lower bound, and this is two times opt, and we're done.Okay. So here's a simple quiz. Now we've proved that the approximation ratio is two, but it could be that maybe by a more smarter proof that we can prove something better. So, the question is, is this algorithm: a, actually a 1.5 approximation or b, no, this approximation ratio two for this algorithm is tight. Well, actually, the answer is B and there is a very simple example. If I just would have a graph with one single edge, well, what's the algorithm going to do? It's going to look at this edge, which is now uncovered, put both vertices into the cover, whereas obviously, putting only one would be sufficient. So here, algorithm gives a solution of size two, opt is one, so the approximation ratio two is tight. So, two does not seem like a very strong bound, of course, we would like to get something better. Unfortunately, this even though many, many computer science researchers looked at this problem and the algorithm we just gave is extremely simple, you would think that probably somebody would come up with something a little bit smarter and get an approximation ratio, which is better than two. Well, this is not the case. Nobody has found anything which is better than two, not even 1.9999. Actually, what is also interesting to note is that okay, maybe we still have some hope that we can get a little bit below two for the approximation ratio, but as the second staple that you see here shows is that it's not possible to get really close to one, but it's impossible to get something better than roughly 1.3, because already computing a 1.36 approximation as you see here, already that problem is NP-hard. So, another interesting observation is that what we did here is, well, we gave an algorithm and we actually proved that no matter what happens, it's always a two-approximation, so it's always at most two times opt. We did that by always putting both vertices of the uncovered edge into the solution. We did that because it's kind of difficult to decide which one to put into the cover. Now what you could do is maybe put the vertex that covers the maximum number of new edges and use that. So, find a vertex with high degree that covers lots of vertices and put that into the cover. Well, if you analyze it, then it could actually be worse than a two-approximation But in practice, it's probably going to be better. So, you have to be careful if you think about something that you could prove in theory, than maybe another algorithm that in theory has a worst bound, maybe in practice, it usually works better. So then, you have to make a decision. Do you go for the guarantee of two or do you go for an algorithm that sometimes maybe in some extreme cases does worse, but often does much better? So, what did we see today? We saw a two-approximation for vertex cover. What we're going to do next time is we're going to do a weighted version of vertex cover, where maybe it's more expensive to install this little piece of software on one computer than it is to install it on another one. And then for that one, we're also going to come up with an approximation algorithm, and this one uses a very important technique called LP relaxation. But that's for next time.