[MUSIC] I have given you an algorithm for the facility location problem, now let us analyse it. As a reminder, these are the primal and dual linear programs that were used in the design and that we will used because of their complementary slackness conditions. And this was the algorithm that I executed on an example for the facility location problem. What we aim to show is that it's a four approximation. Clearly by construction, the algorithm does give you a feasible solution. A solution, which is a set of facilities, and an assignment of clients to facilities. The only problem is, what is the cost of the output? What is the cost of a resulting set? We know that there are two components to the cost. One is the service cost, the cost of traveling from the clients to the facilities, and the second one is the facility opening cost. So, let us analyze these two parts separately. First, the service cost. The service cost, let's look at the same example as we did before. The service cost, for example, for this client, it goes to that facility, the service cost is the length C I J of this particular edge. There are also some clients that are connected to a facility that is not adjacent, that don't have x star iJ strictly greater than 0. For example, this client here with a value 4, gets connected to this facility even though there's no direct connection in the graph defined by looking at the optimal LP solution. Okay, so, how do we bound the cost, the service cost, the sum of the distances of all these client facility paths? This cost is by definition the sum over every cluster. Each cluster corresponds to a facility of the sum for every client in that cluster of the cost of connecting client J to the facility in the center of that cluster, to the facility I sub C for cluster C. And now to deal with these dotted edges, the connection that are not direct. We used the assumption that we have a metric. We used the assumption that connecting j to iC is less then the cost of connecting iC to jC, then going from there to i, and then going from there to j, Cicjc + Cijc + Cij. This cost is less than the sum of the costs on this, that and that connections. That is what we replace Cicj by. And so, here we are and now what we observe is if j belongs to cluster C, then all of these three steps are edges in the graphs. What does it mean that they're edges in the graph? It means by definition of the graph that the x variables, the corresponding x variables, are all strictly positive and now we can use complementary slackness. Xij star is strictly positive, so what does this imply? It implies that the corresponding dual constraint is satisfied with equality, alpha j start is exactly equal to beta ij star + Cij, similarly for XijC. The corresponding dual constraint is true with equality. And similarly for the third one, the corresponding dual constraint is true with equality. And so that gives us upper bounds on these C variables. Cij is at most Cij + beta ij star. Why? Because the beta is a non negative, and therefore, it's at most alpha j star. So, we can take this cost, it's less than the sum of those three costs, and each of those costs in turn is less than the corresponding alpha j star or alpha jc star. So, we add and we obtain the cost of the connection from client j to the facility at the center of its cluster is at most alpha j star + 2 alpha jc star. And then what do we do? And then we remember that in the algorithm, we picked the unassigned client whose alpha star value was minimum, so alpha jc star was the minimum value. So all the clients that went into that cluster have a greater value of alpha j star. And so alpha jc star can be upper bounded by alpha j star. So when we substitute that in there, what we get is, the cost of connecting client j to the facility at the center of it's cluster is at most 2 plus 1, 3 times alpha j star. So, the total output cost is at most the sum over every cluster of the sum over every client in that cluster of 3 alpha j star. Now look at the sum, we can merge these two sums into a single sum. What do we get? We get the sum over every single client, every client appears exactly once here. So this double summation is equal to 3 times the sum over every client of alpha j star. And what is that sum? It's the objective of the dual linear program. So by the duality theorem, this is at most OPT. And so what this proves is that the service cost, the service cost here, is at most 3 times OPT. The cost of connecting all the clients to some facilities with this algorithm is at most 3 times OPT. Now, we need to bound the second part of the cost, and that will be the object of the next section.