TY - JOUR
T1 - Greedy Strikes Back
T2 - Improved Facility Location Algorithms
AU - Guha, Sudipto
AU - Khuller, Samir
N1 - Funding Information:
* A preliminary version of this paper appeared in the Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (1998). ²Supported by an ARO MURI Grant DAAH04-96-1-0007 and NSF Award CCR-9357849, with matching funds from IBM, Schlumberger Foundation, Shell Foundation, and Xerox Corporation. E-mail: sudipto@cs.stanford.edu. ³ Research supported by NSF CAREER Award CCR-9501355. E-mail: samir@cs.umd.edu.
PY - 1999/4
Y1 - 1999/4
N2 - 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. We assume that the transportation costs form a metric. This problem is commonly referred to as the uncapacitated facility location problem. Application 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 algorithm by Shmoys, Tardos, and Aardal, can be used to obtain an approximation guarantee of 2.408. 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 prove a lower bound of 1.463 on the best possible approximation ratio, assuming NP ∉ DTIME[nO(log log n)].
AB - 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. We assume that the transportation costs form a metric. This problem is commonly referred to as the uncapacitated facility location problem. Application 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 algorithm by Shmoys, Tardos, and Aardal, can be used to obtain an approximation guarantee of 2.408. 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 prove a lower bound of 1.463 on the best possible approximation ratio, assuming NP ∉ DTIME[nO(log log n)].
UR - http://www.scopus.com/inward/record.url?scp=0000182223&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0000182223&partnerID=8YFLogxK
U2 - 10.1006/jagm.1998.0993
DO - 10.1006/jagm.1998.0993
M3 - Article
AN - SCOPUS:0000182223
VL - 31
SP - 228
EP - 248
JO - Journal of Algorithms
JF - Journal of Algorithms
SN - 0196-6774
IS - 1
ER -