Greedy strikes back: Improved facility location algorithms

A fundamental facility location problem is to choose the location of facilities, such as industrial plants and warehouses, to minimize the cost of satisfying the demand for some commodity. There are associated costs for locating the facilities, as well as transportation costs for distributing the commodities. This problem is commonly referred to as the uncapacitated facility location problem. Applications to bank account location and clustering, as well as many related pieces of work, are discussed by Cornuejols, Nemhauser and Wolsey. Recently, the first constant factor approximation algorithm for this problem was obtained by Shmoys, Tardos and Aardal. We show that a simple greedy heuristic combined with the Shmoys, Tardos and Aardal algorithm, can be used to derive a better approximation guarantee. We discuss a few variants of the problem, demonstrating better approximation factors for restricted versions of the problem. We also show that the problem is Max SNP-hard. However, the inapproximability constants derived from the Max SNP hardness are very close to one. By relating this problem to Set Cover, we can prove a better lower bound on the best possible approximation ratio.