[MUSIC] I ended the last presentation with QED, quod erat demonstrandum. Actually no, we're not quite done. We still have a lemma who's proof is still pending. So, now finally, I need to prove this last technical lemma. Let me remind you of the statement of the lemma. Let F prime denote the output set of edges, the result of the algorithm. Fix a time during the execution, and say that a set S is active, if it's dual variable is being raised. Then the lemma states that the average cardinality of F prime intersect delta of S is at most two, average over all the active sets. Example, F prime, solid blank lines, active sets, dotted ovals, intersections stars, yellow stars. This is what we need to prove now. So how do we prove this? Another reminder that will enable us to recap the properties of F prime and of the active sets. The algorithm kept raising every dual variable that was unfrozen and such that S was minimal. And then in the int of prime was obtained from the final primal solution x by pruning unnecessary edges. So, let's talk at the properties of F', of the active sets, and their joint properties. The active sets, they're always these joint subsets of nodes, and they always contain terminals. That's what the active sets possess as properties, important properties. Properties of F prime, F prime is a forest and it's leaves are terminals. Joint properties of F prime and of active sets. If we look at a tree, one of the trees of F prime of the output, and assume that it intersects some active sets, then the active sets are subtrees of F prime. And all the leaves of F prime are in active sets. Okay, now with these properties, we're going to be able to prove our lemma. Indeed, this reminds us a little bit of a well known graph theory lemma. Consider any tree T, consider any subset X of its vertices that includes all the leaves of the tree. Then if you look at the average degree of the vertices of X, it's at most 2. The sum of deg(v) over every vertex of X divided by the cadrinality of X is at most 2. This is a graph theory lemma very closely related to what we're trying to prove. Example, here's a graph, a forest. Here's one tree of a forest. Here's a subset of it's vertices. Let me take this tree instead. Here's a proper subset of it's vertices containing all the leaves. The sum of a degrees of those vertices is one plus one, two. Which is less than the result of two times the number of elements of X here. Okay, how do you prove this? Let's do a quick proof of this basic graph theory lemma. Induction. Induction but going down instead of going up. Going down, on the continuity of X. Let's start with X equal to everything, all the vertices on my tree. The sum over every vertex in a tree of a degree is what? It's 2 times the number of edges, that's well known. If you're taking this course and you've reached this point, then you know this. The number of edges of a tree is the number of vertices minus 1. That's well known, if you're taking this course, you know this holds. And therefore, this is less than 2 times the vertex set. Okay, true for X = V. Inductive step. If it's true for a certain set X, then it remains true when removing an internal node from X. Indeed, here is the proof by example. Here is the tree a set x consisting of five vertices. Remove one of the internal vertices, we have a new set x consisting of four vertices. Four vertices, what happens to the sum of a degrees? We've lost an internal vertex. We've lost, three. The sum of the degrees has decreased by three in this case. We've lost one of the elements of X. Cardinality of X has decreased by one. 2 times the cardinality of X has decreased by two. The right hand side has decreased less than the left hand side. So if this inequality was valid before, it's still valid afterwards. So, by induction, the equality remains true throughout and that proves the graph theory lemma. So we have this graph theory lemma, now all we need to do is use it to prove our own approximation algorithm lemma. Let me put them side by side. F prime the output forest. The average degree of the active sets in F prime is at most 2. Graph theory lemma, T a tree X a subset of vertices including all the leaves. The average degree of the vertices of X in the tree is at most two. Compare, very similar. In fact, look at these two pictures that are used as examples, very similar. What the difference? The difference is that S here is not necessarily a single vertex. It can be a subtree of F prime. But look, these pictures are so similar. What is the relation between this picture and that picture? Contraction, contraction. Contract the S's into single nodes and then you go from this picture to that picture, where you could apply this graph theory lemma. Is this a valid transformation? Yes. Yes, [COUGH] when you contract active sets, it does not change the left hand side nor the right hand side. And therefore we can do the transformation, apply the lemma, and it proves our original lemma. And now we can really say QED, we are done. We have completed the proof of our 2 approximation for our algorithm for the standard forest problem. So that's our result. And what can we say about this chapter? What have we learned in this section? We've learned how to use the primal-dual method in a nontrivial way. We have used this for a result for the Steiner forest problem but this actually extends. This method can be applied to many other connectivity problems even beyond. What we have seen is that the primal-dual method is really a greedy technique. We greedily increase x, we greedily increase y. This is really a view point under a certain category of greedy algorithms. We have seen that the dual solution gives us some insight to try to guide our next choices in the greedy increase of x. We have also seen unfortunately that some post processing can be necessary, so it's not technically exactly a greedy algorithm. There's a greedy phase and there's a clean up phase. We have seen also that this is actually a combinatorial algorithm. We have never solved a linear program. Our LPs are just guides, they're not computational tool. All these things make these methods, primal-dual techniques, extremely appealing. They're simple, they're fast in practice. They end up being clever variants of greedy algorithms and for that reason they are quite, quite popular. And so in the next section of this course we will study primal-dual techniques applied to another category of problems, the facility location problems.