Welcome back to the Cousera course on Approximation algorithm. I am Vasan Acquinadad. I'm a teaching assistant for this course and I was also a teaching assistant for the previous course, the part one. I would like to introduce you to a classical problem on approximation envoys. The facility location problem. Suppose you are running a big company that provides some service on the internet. You have customers all over the world and you have to buy and to build some data centers to provide the cells. What you can do is open them up, look at the possible location, and find one. Build a data center at this position and be done with it. But this might be very bad for the service cost. Some customers can be very far from the data center, and the quality of service will be very bad. On the other hand, you can build a data center in every city of the world, then we'll ensure a very good quality of service. But this can be also very bad for your budget because, it might be very expensive to by some many data centers. So what you want to do is to find some good location that are not very expensive and that are enough to provide a good quality of service. So this is the facility location problem. Let's define it more formally and consider a bypartite graph which has on one side possible location for the data center, what we will call the facilities and on the other side, your customers, which we call the clients. Additionally, we have for each facility we have an opening cost, which corresponds to the cost of building the data center. And for each pair of facility and client you have the distance from the client to the facility, the quality of service. This is a formal definition of the input, so let's also talk about the formal definition of the output. The output consists of a set s of the facility, the facilities that we will buy. That doesn't tell us built and the cost of the solution is composed of two sides. So on one side, you have the cost of building the facilities. So the sum of the cost of the facilities and they are in the output set. And on the other side, the distance is from each client to the closest facility of the set. This is the output, a set and the cost which is associated. Let's look at the example. So in this graph, we have the client, the green points, and the facilities which are the squares. In this case, we have three possible locations for the facilities. We have the top most, which costs 3, this one which costs 1, 1nd the bottom one, which costs 2. In this solution, we bought to choose to buy the top most and the bottom most. So the facility cost for the solution is three plus two, five. Now let's look at the clients cost. The client cost is the sum for each client of the edge going to the closest facility. So for example, this client here, the closest path to the facility is the search which costs 1. So the total cost is 1 + 4 + 1 + 3 + 2 + 1 + 4. So the client cost is 16. The overall cost then is the facility cost plus the client cost, 21. Okay, so for this lecture we will assume triangle inequality holds, which means that if you look at pair of client and facility, then the edge that connects the client to the facility is as a smaller cost than any other paths joining these two points, joining this client to the other facility. In the next lecture we will define an integral integer of programming formulation for the problem. We will look at the dual and we will define the primal-dual algorithm which achieve a three approximation.