We have designed the primal dual algorithm for the Steiner forest problem. Now we will prove that it's a two approximation. As a quick reminder, the algorithm has three steps. Initialization set the primal and dual variables at 0. Iteratively make the primal solution feasible while keeping the dual solution feasible by finding x not feasible, raising minimal unsatisfied, do our constraints, do our variables. Until something becomes tight and then choosing with this which edge to add to the primal solution. And third step, pruning the resulting forest to remove extraneous edges. How do we analyze this? First, we observe a few properties satisfied by our solution. Properties, the final solution in the dual y is a feasible dual solution. It was feasible throughout. Property. The final primal solution x is a feasible forest. It's feasible for the primal because that was precisely our stopping condition. Property, our output F prime is also a feasible forest. We remove the trees but preserve feasibility. Moreover, it's leaves are terminals because otherwise there would still be some extraneous edges. Finally the slackness condition. This condition is useful for analyzing primal dual algorithms. So we will need to use some kind of slackness condition. If we take an edge that belongs to the output F prime. F prime is a subset of F. So we know, it also belongs to F. What does it mean that it belongs to F? It belongs to F because x sub e, is equal to one in the final primal condition. How did the algorithm decide to set x sub e to one? Because, the corresponding dual constraint was tied. In other words, the sum over every s containing e of y sub s is exactly equal to c sub e. Or in other words, if x sub e equals one, then c sub e is exactly equal to that sum. If e is an F prime then c sub e is exactly equal to this sum. With that condition we are ready to proceed with the analysis of the cost of the output. What is the cost of the output? It is the total cost of the edges in the output solution. It is a total cost. The sum of c sub e for every at e in the output F prime. But what do we know? We just proved that c sub e is equal to the sum over s containing e of y sub s. So we substitute. So we start by using the complementary slackness conditions. Then what? Once we have this, we have a double summation. What do we do when we have a double summation? We invert the summations, always. It's a rule of thumb. So, sum over e, sum over s, equals, sum over s, sum over e. More precisely sum over e in the output in F prime. Sum over s cut containing e of y sub s equals sum over s, cuts s, of y sub s times sum over e in F prime and also in the cut s of one. A sum of ones that's just a cardinality, cardinality of F prime intersect the cut delta of S defined by S. So this is our bound for the cost of the output so far. Next, how can we upperbound this quantity? This seems complicated. We dont know very much about F prime. We have a sum over many cuts and this ys is very widely. However, if we think back about the algorithm, at every step of the algorithm, we take a certain collection of S's and we raise all the ys's in parallel. They all increase in parallel by the same amount for a certain time interval. So, let's do this upper bound incrementally over time. Let's split it according to these ys's that increase gradually. Let's bound the sum over every time stamp during the execution. The sum over every S that is active between t and t + dt, that is, as did have it's y sub x increased of. And it we split time into two very small time intervals between t and t + dt, all the active y sub s's are increased by an infinitesimal amount, let's call it epsilon. Let's discretize because in computer science we're often more comfortable with discrete quantities. Epsilon times the size of F prime in the. What does it mean, this term active? Active means the dual variable is being raised. Okay. So what is this more precisely, go back to the algorithm. During an iteration, what do we raise? We raise every unfrozen variable ys, such that S is minimal. In other words, active means unfrozen, with S minimal. Okay, so these are active variables. Now how do we upper bound this quantity? Well, we look at the inner summation. The inner summation, we can take epsilon out. How do we bound the sum over s, currently active, of the size of F prime into delta of S. This is the main, remaining question, in order to be able to proceed with the analysis. This question doesn't have an obvious answer. So let's first try a few examples to get some intuition. Here is an example. I have a, my graph is in grey, my tree F prime are the solid black lines. Here, it's a tree not a forest, just by chance. The terminals are, there are four red terminals, two green terminals here. The current active sets, there's three of them. S1, S2, S3 at the time during the execution that we are considering. So I am drawing the final F prime, but the current active sets in the middle of the execution, these are at different times. Okay. So the active sets, there's three of them. This one, this one, and this one. So what do we do? We increase these three dual variables a little bit. Y sub S1, y sub S2, y sub S3. And what can we say about the cardinality of F prime intersect the cuts. S1 has one intersection with F prime. There's exactly one edge of F prime leaving S1. S2 has exactly two intersections with F prime. There are two edges of F prime leaving S2. S3 has one intersection with F prime. There's one edge of the tree leaving S3. So what we cant see is that I put a little star at every intersection here. You see these stars when a solid line, meaning an edge of F prime, intersects a dotted oval, meaning an active set. Four stars. The sum over every active set of the stars of F prime intersect delta of s is the number of stars which is 1 + 2 + 1 = 4. Three active sets, four stars. So the value we're trying to add it on =4 in this example. Another example. Let's say F prime is a line. Let's say every node is an active set. Maybe this is the initial configuration. Then what? Where do we draw the stars? Here. There. Many intersections here. We have eight active sets in this case and how many stars? You can count them. There's 14 of them, 14 stars. Here's another example. Now, F prime is the tree which has a unique central node and many leaves. Let's imagine again, once again that every node is active. Maybe this is initial configuration. Then we have nine active sets and if you count the stars there will be 16 of them. Here is another example, a little bit more complicated. Now we have two different trees in the forest. I drew actually not just F prime but also F- F prime, the edges that got pruned in the third step. For example, at the end of the third step, maybe F consisted of, had this tree here, but these three nodes, they are not terminals. So those three edges, they are pointless. And therefore, in F prime, we have only, leaves are terminals. Okay, so what happens in this case? In this case also, not every node is active. See these two nodes here? They're not in an active set. So still in this case if I look at this forest, which is more, sort of a more general case, if I look at those active sets, S1, S2, S3, S4, S5, I have five active sets. And if I count the stars, one, two, three, four, five, six stars. So now I'm ready to propose a conjecture, which I will state directly as a lemma so you know it's true. Lemma. To upper bound the sum over s currently active of the number of edges of F prime that intersect the cut defined by S. On average, this sum divided by the number of currently active sets is, at most, two. It's about two per active set, on average. We had on every example we saw this was true. It was less than two. In fact, strictly less than two. Okay, so I have this lemma that is true by examples. Let's defer the proof of this lemma for a moment. And now let's finish the analysis of the theorem of our algorithm. [COUGH] Let's finish this analysis, assuming the lemma holds. Recap. The cost of the output can be returned like this. We used complimentary condition to substitute for ce using dual variables. Then, we inverted summations to rewrite this using that term. Then we looked at this over time and we looked at this as a sum over time of the increase in the dual variables. Now, apply this magical lemma. Apply this magical lemma and substitute for this sum. This new quantity here, two times the number of active sets. Much more comfortable quantity. Because now what happens, take the two out. Think about the sum over every t of epsilon, the increment in the dual variables. Times the number of active sets, times the number of dual variables that are increased, whose value increases, sum over time of the number of variables, dual variables that are increased during that time step times the amount of the increase. What is that? If you sum this over all times, you get exactly the total increase in all the dual variables. Sum of ys over all s's. And where this is the final value of all the dual variables. And now this y is a dual feasible solution. We know this is at most opt, so we get at most, two opt. We're done with the theorem, module the proof of a lemma, assuming the lemma holds. We have proved that our primal dual algorithm, is a two approximation. And so, what we will do next is the last step to complete the proof will prove the remaining lemma.