[MUSIC] We have constructed an LP relaxation for the Steiner forest problem. Now, let us build its dual. As a reminder, the relaxation is, we have one variable Xe for every edge e. We want to minimize the sum of cexe, the total cost of the output, such that for every cut S, such that there exists a set Si, there exist two terminals of Si such that S separates those two terminals from one another. The total, the sum of the Xis over every edge crossing that cut must be at least one. And Xe is greater than or equal to zero for every edge. How do we take the dual? The dual is taken automatically when the linear program is in this form. Minimization, the dual is maximization. What do we have? One variable for each edge, one constraint for each S. We define a dual variable y sub s for each set S that is a cut of 2 terminals of sum i. What do we want to maximize? A linear combination of the y sub s with coefficient 1 for each y sub s. So, maximize sum over s of 1 times y sub s. What is our constraint? Here it was created under equal, now less than or equal. Less than or equal, the constraint for e, associated to Xe, is the coefficient here is C sub e, so that will be what we will find here at the right hand side of the constraint. For every edge e of the graph, the constraint is associated to e, the constraint dual to variable X sub e, is that something is less than C sub e. And what is that something? It's the sum of one times ys, one times ys, all the coefficients are zero, one. For every S related to e, by this relation, e in delta of s. In other words, the sum of ys, over every s such that e crosses between s and its complement, must be at most, C sub e. And finally, ys must be non negative, for every s in the set of cuts. So that is the dual of our LP relaxation. If you think about the interpretation of a dual, what does this mean? Let's try to understand it a little bit. We want to maximize the sum of the y sub s, we want to give a value to each cut S. Here's a cut S. We want to give it a value y sub s. And what is our constraint? For any edge e, here's an edge e, if we look at all the cuts that cross e, that e belongs to. Here I drew four of them, the sum of their values must be at most C sub e. The edges with their C sub e must be able to pay to give value to the cuts. Okay, so that's sort of our interpretation of a dual that we're going to use to design a primal dual algorithm. Well, we have so many cuts containing e. We said we had an exponential number. How can we hope to build a solution, a dual solution that will be feasible, such that the sum of the ys's will be at most C sub e? There are so many cuts to consider. The answer to this is that our algorithm will actually not consider most possible cuts. It will only take a few, and only a few of them will have a non-zero value. So we should not be worried that there are so many cuts in this world. We should only be interested in the cuts we're going to take, for which we're going to give a positive value. In a way, the fact that we have many cuts means that we have a lot of freedom in the algorithm. So this would actually be helpful to design a good primal-dual algorithm.