1. We show an approximation preserving reduction from the set cover problem:
Given an instance of the set cover problem we create the following instance of the facility location problem: and set
We also set to be 1 for each .Clearly every solution to the facility location can be transformed to a solution to the set cover problem of the same price and vice versa.
2. We now formalize the facility location problem as a set cover problem. In this formulation there will be an exponential number of sets but we will argue that we can use the greedy algorithm for this instance of set cover in polynomial time.
Given a facility location instance we define the following set cover instance where . We let the set covers the elements of and define its cost to be .
Clearly an optimal solution to the above set cover instance is an optimal solution to the corresponded facility location instance.
Now we argue that, in each iteration, we can find the set that minimizes the cost per element in polynomial time. For two number and let the set corresponded to and be where are the clients closest to facility there are such sets that can be found in polynomial time and one can convinced himself that the set that minimizes the cost per uncovered client is among those sets. Thus we have a -approximation algorithm for the facility location problem.