[MUSIC] Welcome back to the course on Approximation algorithms. Let us continue our study of the vertex cover program. We have designed a linear programming relaxation for vertex cover. Now let us see how we can use it to design an algorithm. As a reminder, here is the linear programming relaxation. For every vertex in the graph there is a variable whose value is between 0 and 1. For every edge in the graph, the sum of the two values of the two variables must be at least 1. And the objective is to minimize the weighted sum of the variables. What can we do with this linear program? First, of course we solve it. Solving it will give us time, values for each of the variables, the optimal values xu star for vertex u, xv star for vertex v, for every vertex in the graph. These values satisfy all the constraints. And the objective is minimized. Now what do we do with this? We need from this to deduce a vertex cover. For that we need to decide for each vertex whether or not we put it in the cover. So what do we do with these values that are real numbers between 0 and 1? If a value is .7 it's like saying a vertex is 70% in the vertex cover. So what do we do to decide whether to put the vertex in the cover or not? We simply round to the nearest integer. So if the value associated to vertex u is at least 0.5, we round to 1. If it's strictly less than 0.5, we round down to 0. This defines an integer value z sub u for each graph vertex. Now we're back to integers, therefore this is an encoding of a set of vertices that will be our output, so that's the algorithm. So here you can see the global view of the algorithm. Step 1, you saw the LP. Step 2, you round the LP solution. And finally, you output the set of all vertices, such that, z sub u is equal to 1. The first thing we can note is that if we look at this algorithm the runtime is polynomial. Solving the linear program can be done in polynomial time, that's our black box. Running the solution takes linear time and then we just get the output. So we do have a polynomial time algorithm, but does it solve vertex cover? Does it give a correct vertex cover? Does it cover all edges? It's a set of vertices in order for the algorithm to be correct, the set output must be a cover of all the edges by vertices. So, let us argue that the output set of vertices is a vertex cover. That it covers all edges of the graph. Does the output cover all edges? Let's focus on one of them. Let's say that uv is an edge in a graph, uv. What can we say about uv? We know that the linear program has an associated constraint, and that this constraint is satisfied by the lp solution. So what we know xu star plus xu star is at least one. This is a fact from the algorithm. What can we infer from this? For example xu star could be 0.7. xv star could be 0.3. The idea, small idea a very, very small idea is if xu star + xv star is at least 1 then at least one of these two values must be greater than or equal to 0.5. Of these two values, at least one must be greater than or equal to 0.5. How does that help? Let's look at the definition of the z sub u, at our choice of integers, our rounding. z sub u is 1, as soon as at least one of the variables, as soon as variable xu star is at least 0.5. So, in the example, xu star is 0.7, xv star is 0.3. This means that zu will be 1, 0.7 is rounded to 1, 0.3 is rounded down to zero. This means that the output set of vertices will contain the vertex u and therefore, that edge uv will be covered. This is general. Since at least one of the two variable xu star, xv star is greater than 0.5, at least one of the two values zu, zv will be equal to 1. And so at least one of the two vertices u or v will be put in the cover and so the output will cover at uv. This is true for every edge in the graph so the output covers all edges. So it is a vertex cover and so our algorithm is correct. In this part we have proposed an approximation algorithm for the vertex cover problem based on the solving a linear programming relaxation and rounding and we have proved that it is correct. That the output really is a vertex cover. Now, what remains is to see how good it is, what is the quality of the output vertex cover.