Consider the following problem. There is a set U of nodes, which we can think of as users (e.g., these are locations that need to access a service, such as a web server). You would like to place servers at multiple locations. Suppose you are given a set S of possible sites that would be willing to act as locations for servers. For each site s ? S, there is a fee fs ? 0 for placing a server at that location. Your goal will be to approximately minimize the cost while providing the service to each of the customers. So far, this is very much like the Set Cover Problem: The places s are sets, the weight of a set is fs, and we want to select a collection of sets that covers all users. But there is one additional complication. Users u ? U can be served from multiple sites, but there is an associated cost dus for serving user u from site s. As an example, one could think of dus as a distance from the server. When the value dus is very high, we do not want to serve user u from site s, and in general, the service cost dus serves as an incentive to serve customers from nearby servers whenever possible. 2 So here is the question, which we call the Facility Location Problem. Given the sets U and S with associated costs d and f, you need to select a subset A ? S at which to place the servers (at a cost of ? s?A fs) and assign each user u to the active server where it is cheapest to be served, mins?A dus. The goal is to minimize the overall cost ? a?S fs + ? u?U min s?A dus. Give a ?(n)-appoximate algorithm for this problem.s

Consider the following problem. There is a set U of nodes, which we can think of as users (e.g., these are locations that need to access a service, such as a web server) You would like to place servers at multiple locations. Suppose you are given a set S of possible sites that would be willing to act as locations for servers. For each site s E S, there is a fee f, 20 for placing a server at that location. Your goal will be to approximately minimize the cost while providing the service to each of the customers. So far, this is very much like the Set Cover Problem: The places s are sets, the weight of a set is fs, and we want to select a collection of sets that covers all users. But there is one additional comp cation. Users u E U can be served from multiple sites, but there is an associated cost dus for serving user u from site s. As an example, one could think of dus as a "distance from the server. When the value dus is very high, we do not want to serve user u from site s, and in general, the service cost dus serves as an incentive to serve customers from "nearby" servers whenever possible. So here is the question, which we call the Facility Location Problem. Given the sets U and S with associated costs d and f, you need to select a subset AC S at which to place the servers (at a cost of LsEA f.) and assign each user u to the active server where it is cheapest to be served, min.EA ds The goal is to minimize the overall cost Give a ?(n)-appoximate algorithm for this problem. Consider the following problem. There is a set U of nodes, which we can think of as users (e.g., these are locations that need to access a service, such as a web server) You would like to place servers at multiple locations. Suppose you are given a set S of possible sites that would be willing to act as locations for servers. For each site s E S, there is a fee f, 20 for placing a server at that location. Your goal will be to approximately minimize the cost while providing the service to each of the customers. So far, this is very much like the Set Cover Problem: The places s are sets, the weight of a set is fs, and we want to select a collection of sets that covers all users. But there is one additional comp cation. Users u E U can be served from multiple sites, but there is an associated cost dus for serving user u from site s. As an example, one could think of dus as a "distance from the server. When the value dus is very high, we do not want to serve user u from site s, and in general, the service cost dus serves as an incentive to serve customers from "nearby" servers whenever possible. So here is the question, which we call the Facility Location Problem. Given the sets U and S with associated costs d and f, you need to select a subset AC S at which to place the servers (at a cost of LsEA f.) and assign each user u to the active server where it is cheapest to be served, min.EA ds The goal is to minimize the overall cost Give a ?(n)-appoximate algorithm for this