[MUSIC] Now that we have a healthy relaxation manage tool for Steiner forest we're ready to start designing a primal dual algorithms. These are the primal dual pairs, one primal variable for each edge. One dual constraint for each edge, one primal constraint for each cut, one dual variable for each cut. The constraints can be seen, visualized for the primal if you focus on the one particular cut, you look at the edges crossing the cut. The sum of the axis for all these edges must be at least one. The dual constraint, can be visualized by focusing on one particular edge looking at all cuts crossing that this edge crosses. The sum of the y axis for all these cuts must be at most C sub e. So, that's our pair, our primal dual pair. Let's get started. The primal dual pairs, as reminders, are on top of the screen. Initially, as we did before in our previous example, we start with x 0 y 0, every variable at 0. The dual variables, the dual y is feasible, because it satisfies the upper bound. The primal is not feasible. All zero does not satisfy this constraint. So what do we do? We're going to try to make x satisfiable. We'll try to make x feasible. While X is not yet feasible, what we do is we get to choose a particular X sub e and set it to 1. How do we choose this X sub e? We going to be guided by the dual constraint corresponding to X sub e. So what we do is we take Y, we raise y as much as possible, keeping it feasible, until we are blocked by some constraint. Some constraint becomes tight, a constraint associated to e and that's the x sub e that we set equal to 1. We repeat this until X is feasible. And that is the general scheme of the primal, dual algorithm. Many unknowns remain. How do we raise y? We have a current y, which is all 0. We have to choose some variable to increase. Which variable do we choose? What we did is we just picked any one that would help. We just picked any constraint that would be where it would be helpful. Now we need to be more careful because of all these costs. So, initially, what we have is, we have all these terminals. The red terminals are trying to connect to one another. The green terminals are trying to connect to one another. Initially, all the Ys are zero for all the cuts. What do we do? We start from the singleton cuts. This is a cut. The set S consists of a single terminal, v minus S is everything else. We know that the sum of the x sub e's for every edge crossing this cut should be at least one, and currently it's zero. Same thing for the singleton cut around this terminal, that one, that one, that one and that one. So all these cuts are currently not satisfied. All these constraints in the primal are currently not satisfied. So what do we do, we take all these dual variables Ys is the best and substitute this to all these unsatisfied constraints. And we raise all of them, some of them initially in parallel, that is. Every Y sub s, is increased by epsilon. And we repeat, continue, continue, increasing, continuously, by infinite decimals. There are other cuts, such that the corresponding, their primal constraint is not satisfied. For example, if we take a cut consisting of these two terminals together these two red terminals must be connected to the other two red terminals. So some x should cross. So the sum of the x of these should be at least one but it's zero. Well we do not worry about those yet. Right now, we only worry about the minimal cuts, cuts that do not contain any other not-yet-satisfied cut. Okay, so, we take all the y sub s's that correspond to the cuts s that are not satisfied. The primal concern is not satisfied and they're minimal. They are these singletons here. And we raised them all, until something happens. Until some edge suddenly gets in the way. Suddenly, for this edge e, what we have isthe value of this ys plus the value of that ys is equal to ce. At this point we cannot raise these two values any more. This constraint is tight. So what do we do? We buy this edge, we take this edge, we set xe equal to one. This edge will be in our solution. Then, how do we continue? We continue raising some y s's, but now, there will be different collections of y s's. Which cuts do we now focus on? The cuts we had before, they were good. The two little cuts here, those singletons, now they have edges crossing, so now those two constraints are satisfied. But the next constraint that is not satisfied is the one associated to this pair together. They're connected, but it's not enough. Some edges must come out of this cut. So now, we have this singleton constraint, that singleton constraint, that one, that one and this one. Five minimal constraint in the primal that are not satisfied. What do we do? We take the corresponding five dual variables in a dual, and we raise them continuously by epsilon until something gets in the way. Some constraint becomes tight. In this case, I say, for example, it's this one here, the constraint associated to this edge. This y-sub-s was raised, that y-sub-s is raised, until their sum becomes equal to the cost of this edge. At that point we stop. We buy this edge. We set x-sub-e equal to one for that edge. Now, the constraint is tight. We cannot increase these ys's anymore and we move on to the next iteration. Next iteration. So now, what are our minimal and not yet satisfied constraints? These three singletons and this cut. This cut, we need an edge cutting out of it, we have 0 so far. We take all these y s's, and we increase them in parallel simultaneously until, a constraint becomes tight. Say this one. At this point, the sum of these two y s's will be equal to the cost of this edge. Again, we buy this edge. We have a new set of constraints, these three cuts that are not yet satisfied. We raise ys for these three cuts until some constraint becomes tight. We buy this edge, these two constraints are now satisfied. And the y s's are tight. And our new sets will be just two sets. Again, we have raised y s for these two sets until some edge becomes tight, and then we bite, and then we're done. So, that's an example of execution of an algorithm. What was the algorithm? The algorithm is, and that is the result. A feasible x. And that is the duo result here a feasible y. So, here is the proposed algorithm. We start from x and y all equal to one. As long as x is not a feasible solution, what do we do? In parallel, simultaneously, we raise every y sub s that is not yet frozen, that does not yet belong to any time constraint, and that belongs to a minimal S. So we look at the minimal cuts that are not yet satisfied, that still need some edges coming across, and for those, we raise every unfrozen ys. What happens, we stopped once we reach a time constraint associated to a certain edge E and this is a dual constraint. We take the corresponding primal variable and X sub e and we set it to one. And we freeze all the ys's that belong to time constraints. So that is the proposed algorithm for Steiner forest. I say proposed, because this is actually a two part design of algorithm. This is not quite the end of the story. For the designing the algorithm, we'll need to do a little bit more work.