[MUSIC] We are trying to use the primal dual technique to design an approximation algorithm for Steiner forest. So far, we've tried the standard technique. Now we will see that we need a little twist for it to work for Steiner forest. This is where we were, the idea so far. We start with x all 0, y all 0. y is feasible, x is not. We repeat, as long as x does not correspond to a feasible solution, we look at every ys that belongs to minimal cut s, such that we don't yet have a net going across s. In parallel, we raise every unfrozen such y sub s. We stop when we get a tight constraint, corresponding to sub edge e. We take that edge, e, we take that x sub e, and we set it equal to 1. So x keeps increasing, always remaining an integer, y keeps increasing in a continuous manner. And as soon as we do this, whenever we have a constraint that becomes tight, we buy at e and we freeze ys. Now, does this work in general? We saw an example where they seem to work. But is this correct in general? Do we ever get stuck? Is it possible that x is not yet satisfiable, but that every y sub s is frozen, so we cannot raise any of them? Let's see. Is it possible that we get stuck and x is not yet feasible? How can x not be feasible? Because there is a cut such that we have not chosen any edge going across the cut. There is a cut such that x sub e is 0 for every edge crossing the cut. Why can we not raise some of the y(S)'s there? If we cannot raise y(S) for this cut, it's because it's frozen. And why is it frozen? It's frozen because for some edge in the cut, the constraint is tight, but if the constraint is tight, then by definition of the algorithm, we would have chosen to put variable x(e) in the solution. x(e) would be equal to 1, edge e would be in the solution. So in the end, x is a feasible solution. Let me repeat this argument. I claim that with the algorithm, the output is always a feasible solution x. Why? Assume not, let's do a prove by contradiction. x is not feasible, then there exist a cut separating two terminals such that there's no edge of x that goes across. Take a minimal such cut. Why did we not raise y sub s for that cut s? It's because y sub s is frozen. Why is y sub s frozen? It's because it appears in some tight constraint. What is that constraint? It's associated to an edge e that belongs to this cut. The constraint associated to this edge e is tight, therefore by definition of the algorithm, we would have put x(e) in the solution. So that contradicts the idea that no e of the cut is in the solution. Okay, so this proves that the output is feasible. We never stop until we have something that really connects all the terminals on every Si. So, we have this primal dual algorithm. We have some final value of x, final value of y and they are both feasible. We can proceed. The next step of the primal dual algorithmic design is to relate the value of x to the value of y. And that will be useful to upper bound the cost of our output solution x. So what is the output cost of this algorithm? Not good, not good. This algorithm actually does not give you a good approximation. It does not give you any constant approximation at all, in fact. Let's prove it by example. Consider this graph, two terminals, the two red terminals that want to connect to one another. The graph is a tree with edges connected to this terminal with cost 1 through 8 and then 18. Run the algorithm. It's a good exercise to execute this algorithm on that input. First step, a singleton active terminal, another singleton active cut. They both increase until this value reaches 1, and then that edge has a cut of 1. So this edge becomes tight. The dual constraint for this edge becomes tight, so we stop. We freeze this variable. We buy that edge, the edge of cost 1. Next step. Next step in the iteration. Now the cut contains here, two vertices, the red one and this black one, and that cut is still active. They go up, up, up, up, these two variables y s, until they reach 1. At that point, what happens? At that point this edge becomes tight. This edge becomes tight, because it was crossed by the original ys that has value 1. And it's crossed by this one that now has reached value 1. So 1 + 1 is 2. The constraint is tight, we stop, we by this edge, we freeze the cut and we get ready to go to the next iteration. This ys, by now it has reached value 2. Continue, the new minimal cut is this one containing three vertices. It's not drawn, one black, one red and two black vertices and we're going to raise this ys from 0 up and up and up. Continue raising this one at the same time until, 1. When it reaches value 1, then this edge now is crossed by three y(S)s. The initial one, value 1. The second one, value 1, and the new one, the current one that is being raised. When it reaches value 1, this constraint becomes tight. Where by this edge, etc., etc., etc., you can see how this will proceed, until at some point we have bought all these edges. We have this cut that is now our active cut, as long as that one. We increase each of them. When this one reaches value 1 and that one at that point has value 9, 1 + 1 + 1 + 1 + 1 + 1, stop by this edge of cost 18 and finally, finally the two red vertices are connected to one another and we're done. We're done. We could output this tree and what is the cost of this tree? 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 18. I don't what that adds to but it's a lot. Meanwhile, what is the optimal value? 18, to connect the two retinals to one another. It suffices to buy a single edge of cost 18. So the output cost is way, way more than it should be. This is not good. What were we doing? What are we doing buying all these edges here? They're useless, there was no point. But the thing is, the way the algorithm is designed, it doesn't know really. It's trying to grow a solution from this terminal that is trying to reach out to reach the other terminal, but it doesn't know which way to go. So it tries going out every possible way, just in case one of them works. And one of them will work eventually. But in the meantime, it wasted all of its time going down all of those branches. So here's the idea. Many edges in the output are useless. Prune them. Prune the useless edges. That's kind of silly, but it's going to be very helpful. Very helpful. Look at this example. This was our output. Very bad. Let's prune it. These edges are not useful to connect two terminals of SI together. Let's remove them from our solution. Then we get this new solution, of course 18, that is optimal. So we got lucky here. And what can we prove in general? In general, we get to have a modified algorithm with a pruning step and we will show that it's a good algorithm. So here is the algorithm. The algorithm that we will now analyze successfully has three steps. One, initialization. So, we write the primal, we write the dual and we start with x = 0, y = 0. Second, the iteration, where we keep setting some variables of x to 1 and raising continuously some dual variables ys's. As long as x is not yet a good solution. What do we do? We look at the particular set of cuts. The minimal cuts that are not satisfied, that don't have any edges going across, and that need to have edges going across. Cuts separating pairs of terminals that belong to the same Si. For each of those, we raise the unfrozen ys's in parallel. We stop when the constraint becomes tight, and we set Xe equal to 1 for that constraint. And we freeze the ys's in all the tight constraints, so that's the second step. Third step, let F be the set of edges defined by our solution at the end of the second step, defined by x. We take all the edges of F, say in reverse order. Maybe it's a little simpler for the analysis and if these edges are necessary, if it is not on the path that is necessary to connect two terminals that are in the same SI then we get rid of it. That's the algorithm. What are we meant to prove? We will prove that this algorithm is a 2-approximation for the Steiner forest problem. So that's a beautiful, beautiful result. We've done most of the work already, actually. We only have one idea that is still left to prove, but most of the ideas were already present in the design of the algorithm. So now we will proceed and show this theorem.