[MUSIC] In this chapter we're going to design a primal dual approximation algorithm for the Steiner forest problem. The Steiner forest problem appears in settings such as VLSI, optical and wireless communication, transportation and distribution systems, and network design questions in general. What is the Steiner forest problem? The input is a graph with edge costs. I drew a graph. I wrote the costs on the edges in this picture. In addition, you have certain subsets of vertices called terminals. In this case, I have two red terminals, two green terminals, and two purple terminals. The others are all black. It's about connecting subsets of vertices. So, what do we want to do? Here is the output. The output is a connection of edges, the red edges in this picture, this one, these two, this one, and those two, such that each subset of terminals is connected. The red terminals are connected by this path. The green terminals are connected by that path. The purple terminals are connected by this path. And the goal is to minimize the cost of the edges you choose. In this case, the cost is 6 plus 3 plus 4 plus 1 plus 2 plus 8. 24. So that is the Steiner forest problem. What can we say about this problem? What is known about it? There's a special case that is older and very well studied. The Steiner tree problem. The Steiner tree problem is a case where you have just a single subset of terminals. In this example, I put the terminals in red. We have a graph, we have dendrites, we have four red terminals. And if we wanted again to choose edges such that the subset is connected, and the cost of the edges should be minimized. So we'll start as the warm-up by studying this Steiner tree problem and then we will move on to the general Steiner forest problem. So, if you compare Steiner forest to Steiner tree, you can see that in the Steiner forest form, you have a connection of subsets of terminals. In the Steiner tree problem you have a single subset of terminals. In both cases you want to achieve some connectivity requirements. In the Steiner Tree problem, connect all the terminals in the group. In the Steiner Forest problem, connect all the terminals in each of the groups of terminals. So let us proceed to design an algorithm for the Steiner tree problem first.