Greedy strikes back: Improved facility location algorithms

A fundamental facility location problem is to choose the location of facili ties, such as industrial plants and warehouses, to minimize the cost of sat isfying the demand for some commodity. There are associated costs for locat ing the facilities, as well as transportation costs for distributing the co mmodities. We assume that the transportation costs form a metric. This prob lem is commonly referred to as the uncapacitated facility location problem. Application to bank account location and clustering, as well as many relat ed pieces of work, are discussed by Cornuejols, Nemhauser, and Wolsey. Rece ntly, the first constant factor approximation algorithm for this problem wa s obtained by Shmoys, Tardos, and Aardal. We show that a simple greedy heur istic combined with the algorithm by Shmoys, Tardos, and Aardal, can be use d to obtain an approximation guarantee of 2.408. We discuss a few variants of the problem, demonstrating better approximation factors for restricted v ersions of the problem. We also show that the problem is max SNP-hard. Howe ver, the inapproximability constants derived from the max SNP hardness are very close to one. By relating this problem to Set Cover, we prove a lower bound of 1.463 on the best possible approximation ratio, assuming NP is not an element of DTIME[n(O(log log n))]. (C) 1999 Academic Press.