[MUSIC] I have presented a simpler primal dual algorithm for the facility location problem. It turns out that it also had the better analysis or better approximation ratio. So let us do the proof now. As a reminder, a facility is blocked if the sum of the beta ij is exactly equal to fi. And client is blocked if alpha j is greater than or equal to cij for some blocked i. And this is the condition to have an edge in the graph between j and i. We had an algorithm for to build a maximal dual solution starting from all zero raising the alpha js synchronously and raising the beta ijs as needed to try to satisfy all the constraints. There was the dual part of the algorithm, and then with that, we decide which facilities to open among the block facilities, and which clients to assign or which clients within distance of at most three of the open facility in our graph. Okay, let's go to the analysis. Clearly the algorithm can be executed in polynomial time. What is the cost? It's a sum of two terms. The sum over every cluster. Of the cost of opening the facility i sub c that is at the center of cluster c. Plus when I say center, I just mean the one to which every client in c will go to, will be assigned to. Plus the sum over every client j in that cluster of the cost of travelling between facility i sub c and client j. Now, what do we do with the facility opening cost? That is easy. We know the facility is blocked. So we know that fic is equal to the sum over every adjacent client. Of data icj. Here's the facility, here is one of the clients. So, what we can say is if we take this sum and extract from it, those clients that are adjacent to i sub c, a distance exactly one. What we get is fic + the sum over the adjacent j of c icj is a sum of beta icj + cicj. And what is this. This is exactly alpha sub j. It's exactly alpha sub j why? Because whenever we have an edge in the graph, alpha j is equal to beta i j plus c i j. We know we have this equality so this sum here. It's exactly equal to alpha j. So this is good. This is part of a dual solution. So we have a good bound here for some of the opening cost, and part of the connection cost in cluster i. What remains, what is more difficult, is some of these clients are not directly neighbors of i sub c. They're at some distance in the graph, there a distance three from i sub c. That's the second part of the analysis. J is a distance three from i of c. Meaning, j is adjacent to a facility h, that is adjacent to a client k, that is adjacent to the facility i sub c. What can we say now? If there's an edge then alpha is greater than the cost of the edge. So alpha k is greater than the cost of the edge. Alpha K is also greater than the cost of this edge. Alpha J is greater than the cost of this hedge. Combined, alpha K plus alpha K plus alpha J is greater than the cost of this hedge plus the cost of this hedge plus the cost of this hedge. And remember. We are in a metric space. We can apply the triangular inequality. We can say the cost of connecting j to facility ic is less than the sum of the three costs, which is less than alpha j plus alpha k plus alpha k, alpha j plus 2 alpha k. That's a good start, we are almost done with the analysis. We just have one more observation to make. Because the algorithm always picked among the pending facilities, the first one that was blocked. Then, that's the settle point actually. You can convince yourself that i sub c was blocked before h. And you can convince yourself that alpha k is less than moving towards to j, why? Because alpha k was raised, raised, raised until it was blocked. Blocked y, blocked perhaps because of ic, in which case that triggers the event of creating this cluster, or because of some other facility. But then that triggers the event of creating another cluster. And so h never has a chance. Okay, so now we can substitute alpha k less than alpha j, and we get the cost of connecting j to its facility is at most 3 alpha j. And now, now we're done. Now we're done, we can just take this and combined with what we had on the previous slide, and we will basically finish the analysis as usual, together. The output cost is a sum over every cluster of FIC, plus the sum of the connection costs which can be split into two parts depending on whether the client j's adjacent or not adjacent. And if it's adjacent we can combine connection costs to and cost f. Replace by the beta's and then we get the other j's, okay, and then other j is less than three. Alpha j, and then what do we have? Some over cluster C and some over client of C of 3 alpha j. This is a destroyed sum, so it's at most three times the sum of alpha j over every client j. And this is the dual objective value. And since, we have a dual feasible solution, this is at most, this sum is at most OPT and so the output cost is at most 3 times OPT. We have proved that the algorithm is at 3 approximation for facility location. Three is better than four, so this algorithm is better than the one I had presented before. However, that's not the end of the story. I will tell you the last word, last current word as of today on the facility location problem.