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 -