[MUSIC] We have designed a primal-dual algorithm for the facility location problem. And then we have proved that the service cost of the resulting assignment is at most three times opt. It remains to analyze the cost of opening all the facilities. As a reminder, once again, here is the LP relaxation and there is its dual. And here is the algorithm that we are analyzing. We're going to use the complementary slackness conditions as usual. So how do we bound the cost of opening all the facilities? Let's look at this example once again. We have two facilities that are open. The cost of opening the facilities is four for this one plus four for that one, equals eight. How do we prove, how do we bound this eight in general? So the cost of opening other facilities is the sum over every cluster output by the algorithm of the cost of opening the facility i sub c that is at the center of that cluster. What do we observe? We observe that if facility i sub c is open, then by definition of the algorithm, we opened the cheapest facility adjacent to our unassigned client j sub c. In other words, we open the facility whose crossed f sub i sub c is the minimum of fi over all facilities i that are adjacent to j sub c in the graph. The minimum is less than the average, it's less than the expectation, it's less than the average over the distribution x star, think about this. By the primal constraint if we look at client j sub c, it's assigned professionally to a collection of facilities i. How much of is it is assigned to facility i? x* sub i, j sub c. The sum of all these x stars is equal to one. The constraint says it's greater than or equal to one but actually it's equal to one. There's no reason for it to be strictly greater than one. Okay, so x sub star sub i, j sub c. As I ranges over all facilities defines a distribution. It's a collection of numbers, that are all non-negative and that sum to one. So x star sub something j sub c is a distribution over facilities. And what is this sum? This is an expectation over this distribution, is the expected cost of facility i, When i is drawn according to this distribution among all the facilities adjacent to j sub c in the graph. The expectation is at least as large as the minimum. So, f i sub c is less than the sum of i of x star i j sub c times f i. Next, let's use the primal constraint. The other primal constraint. The one that says that x star i j sub c is less than or equal to yi star. We can substitute that in this inequality. And so what do we get? The total cost of opening all the clusters, the sum of FIC is at most the sum of all clusters, of the sum of all facilities adjacent to j sub c. The central client in this cluster, of y i star times f i. Now we're almost done. We're almost done. We look at this, we think about this algorithm. What does the algorithm do? Once it chooses which facility to open, it connects to it every client that is a distance two, two or less from j sub c. So at this point every client who in particular is adjacent to i will be connected to i sub c. And so what's going to happen here is that this gives you a partition. A partition of the facilities, and so this is a disjoint sum. It's a disjoint sum, so it's at most the sum of yi*fi. And so it's at most OPT because this is part of the primal objective. And so, what we have altogether is the service cost is, at most, three times OPT. The facility opening cost is, at most, OPT. And so we have a four approximation for our algorithm. We have a four approximation. How happy are we with this? If this was 1997 we'd be very happy because this is a well know, basic, classical problem of optimization. And this would be the first constant factor approximation. But then if we think about it, we're not so happy because four doesn't seem like a tight result. In particular, if you go back and look at this quantity here, this is only part of the primal objective. So when we say it's less than OPT, there's room for improvement there. So, here we may be suboptimal. Our analysis may be loose. Maybe it's possible to do better. Second reason to be not quite, not completely on the cloud. The second reason is the first step of the algorithm required solving the primal and the dual LPs exactly. So it required using an algorithm for solving, a toolbox for solving LPs. And that is more costly than to accommodate all approaches. Actually, it's possible to get a better algorithm that is purely communitorial but not a primal dual algorithm. And that gives you not a four but a three approximation. So I want to just outline this algorithm and I will do that next. So that will be the next section.