[MUSIC] In this section I will give you an algorithm that is historically the first constant factor approximation for the facility location problem. We have seen a linear programming with accession for facility location. Here it is. We have seen the dual-linear program. There it is. Now we're going to use both the primal and the dual to design an algorithm for facility location. Here is how the original algorithm worked. First, solve the primal and the dual linear programs optimally. Let y*, x*, alpha*, beta* denote the optimal solutions of the primal and of the dual linear program. We know that the set is fine, the complimentary slackness conditions. Then we use these solutions to decide which facilities to open and where to assign the clients. We do this iteratively. As long as some clients are still not yet assigned to a facility, we choose one particular unassigned client, j sub c for a new cluster c. Which one do we choose? We use the dual for this, we choose the unassigned client who's alpha star value is minimum. That is we look at the dual optimal solution to decide which client to worry about next. Then, we consider all the facilities that are fractionally used by that client. That is, all the facilities so that the external value of i j sub c is not negative. It's strictly positive. Among those, we look at the cheapest possible facility. And our goal that cheapest facility, we call it i sub c and we open that facility. Okay, so that's how we choose the next facility to open. And who is going to go to that facility? The clients who are going to go to be assigned to that facility will be all assigned clients, such that either they directly connect to that facility. That is x star icj is strictly positive. Or there is some intermediate facility with xijc strictly positive, and xij strictly positive. Let me explain this on an example. So to explain this algorithm, I will execute it on the particular example. I will start with a solution of the primal and dual LPs. Here it is. Here, I represented the solution where in green I have all the facilities. The green squares are the facilities. The numbers are the costs, to open those facilities. The blue circles are the clients. And the black numbers next to them are the dual optimal value of j star. And finally, what are the edges? You draw an edge between a client and a facility if the corresponding xij* is strictly positive. So, we will use this graph and those values to decide which facilities get opened and to which facility each client gets assigned. So let's get started. How does the algorithm work in the first iteration of the wire loop? First you pick the unassigned client with minimum value of alpha j star. Initially, nobody's assigned. You look at all these blue circles and you choose the one that has the minimum number next to it. One. There it is. So take this client. You will focus on this client, look at all the facilities next to it. Connected to it by an edge. There they are. Two facilities. Of those two, you pick the cheapest one, this one. You will open this facility. This facility gets opened at a cost of four. Finally, you decide who to assign to this facility. Who will you assign? You will assign to this facility all the clients that are at hop distance two from the vertex you started from, the client you started from. So in particular, all the clients that are adjacent to that facility get connected to it. But also, from this client, client one, in one step we can get to that facility and with the second step we can reach that client. So that client also gets assigned to this facility. So we take all the clients that are a distance two from this vortex. At most two, and we assign them to this facility. That's the first iteration. Now all the vertices over there are assigned. Let's continue, second iteration. Second iteration, of the remaining clients that are not yet assigned, take the one with the minimum value of alpha j star. There's another one here, here it is. So we pick this client and we start from here. What do we do? We look at all the facilities connected to it. There's three of them, this one, this one, and this one. Okay, the costs are, facility opening costs are 5, 7, and 4. So the minimum is 4, and so that's the facility that we will open next. We will open facility number 4, and who are we to connect to this facility? We will connect every client that is reachable from this one, by a path of length two. That is either going through this facility to all the other neighbors, these vertices, these clients all get assigned to facility four or going this way, these already assigned so we don't go there, but this one, or that way. This client is reachable from here by a path of length two. So we assign this client and that client and all those clients to the new facility. And that's the end of a second iteration. Now look at this, all the clients are assigned. So we're done with the algorithm. We have executed the algorithm. The result has been opening two facilities, and assigning one, two, three, four, five, six clients to this facility. And the remaining clients to that facility. So that was the execution of an algorithm for the facility location problem. Now we will analyze it.